【38】求链表倒数第k个结点

题目:输入一个单向链表(只有指向下一个结点指针),输出链表中的倒数第k个结点。

分析:

1. 一个单向链表只有指向下一个结点的指针,所以我们无法得到前面一个结点的指针,所以不能通过最朴素的枚举法来求出。

2. 现在要求出倒数第k个结点。现在用一个指针枚举是无法求出,但是我们可以使用两个指针法(非常重要)。

   初始化设置两个指针p1和p2,p1和p2都指向链表的头结点。我们可以先让指针p1指针先走到第k个结点,下一步开始两个指针p1和p2一起走,当p1指向链表最后一个结点的时候p2指向即为倒数第k个结点。

   为什么呢这个方法是正确的?

   当p1指向第k个结点的时候,p2和p1相差k个结点,所以当p1指向尾结点的时候,p2指向的即为倒数第k个结点。

代码:

//链表结点
struct ListNode{
    int value;
    ListNode *nextNode;
}; 

//求倒数第k个结点
ListNode* GetKthFromTail(ListNode *headNode, int k){
    //数据不合法
	if((headNode == NULL) || (k <= 0)){
	    return NULL;
    }
    ListNode *p1 = headNode;
    ListNode *p2 = headNode;
    int count = 1;
    //让p1先走到第k个结点
	while((count < k) && (p1 != NULL)){
        p1 = p1->nextNode;
        ++count;
	}
	//判断数据合法性
	if(p1 == NULL){
        return NULL;
	}
	//两个指针一起走,当p1指向尾结点是p2指向即为倒数第k个结点
	while(((p1->nextNode) != NULL)){
        p1 = p1->nextNode;
        p2 = p2->nextNode;
	}
	return p2;
}
时间: 2024-12-30 16:52:24

【38】求链表倒数第k个结点的相关文章

[程序员面试题精选100题]9.链表中倒数第k个结点

题目 输入一个单向链表,输出该链表中倒数第k个结点.链表的倒数第0个结点为链表的尾指针. 思路一 因为是单向链表,只有从前往后的指针而没有从后往前的指针.因此我们不能倒序遍历链表,只能正序遍历.假设整个链表有n个结点,那么倒数第k个结点是从头结点开始的第n-k-1个结点(从0开始计数).我们只需要得到链表中结点的个数n,那我们只要从头结点开始往后走n-k-1步就可以了. 因此这种方法需要遍历链表两次.第一次得到链表中结点个数n,第二次得到从头结点开始的第n-k-1个结点即倒数第k个结点.时间复杂

剑指Offer之链表中倒数第k个结点

题目描述: 输入一个链表,输出该链表中倒数第k个结点. (hint: 请务必使用链表.) 输入: 输入可能包含多个测试样例,输入以EOF结束. 对于每个测试案例,输入的第一行为两个整数n和k(0<=n<=1000, 0<=k<=1000):n代表将要输入的链表元素的个数,k代表要查询倒数第几个的元素. 输入的第二行包括n个数t(1<=t<=1000000):代表链表中的元素. 输出: 对应每个测试案例, 若有结果,输出相应的查找结果.否则,输出NULL. 样例输入: 5

C语言实现输出链表中倒数第k个节点_C 语言

本文实例展示了C++实现输出链表中倒数第k个节点的方法,分享给大家供大家参考之用. 运行本文所述实例可实现输入一个单向链表,输出该链表中倒数第k个节点. 具体实现方法如下: /* * Copyright (c) 2011 alexingcool. All Rights Reserved. */ #include <iostream> using namespace std; int array[] = {5, 7, 6, 9, 11, 10, 8}; const int size = size

剑指offer系列之十三:链表中的倒数第k个节点

题目描述 输入一个链表,输出该链表中倒数第k个结点. 举一个简单的例子,比如链表{1,2,3,4,5},如果要返回倒数第二个节点,也就是k=2,就相当于正数第5-k+1=4个节点,所以我们可以采用两次循环:一次循环得到链表的结点个数:另一次循环则是从链表中找到第n-k+1个节点.虽然是两次循环,但时间复杂度是O(n),需要注意的是,这里仍然需要对链表的边界条件进行判断.基于这种思路写出如下代码: public ListNode FindKthToTail(ListNode head,int k)

防御性编程习惯:求出链表中倒数第 m 个结点的值及其思想的总结

防御性编程习惯 程序员在编写代码的时候,预料有可能出现问题的地方或者点,然后为这些隐患提前制定预防方案或者措施,比如数据库发生异常之后的回滚,打开某些资源之前,判断图片是否存在,网络断开之后的重连次数或者是否连接备用网络,除法运算中的除数问题,函数或者类在接受数据的时候的过滤情况,比如如果输入一个指针参数,是否需要判断是不是空指针?输入一个字符串参数,是否需要判断字符串空否--总的来说就是防止出现不可预见的事情,设计出鲁棒性的代码. 看下面的例子 输入一个链表,输出链表中倒数第 m 个结点额内容

求链表的倒数第N个节点

最近看一本书上有求链表的倒数第N个节点,简单实现了下 链表,实现方案如下 1.不借助链表长度顺序遍历倒数第N个节点 GetReserveN就是如此实现. 2.当然如果链表记录了节点长度也可以直接正序遍历出来 第lenth-N个节点就是倒数节点. template<class T> class LinkedList { public: operator T(){return m_data;} virtual ~LinkedList() { if(m_size!=0) Clear(); } voi

CareerCup之2.2 寻找单链表倒数第n个元素

[题目] 原文: 2.2 Implement an algorithm to find the nth to last element of a singly linked list. 译文: 实现一个算法从一个单链表中返回倒数第n个元素. [分析] (1)创建两个指针p1和p2,指向单链表的开始节点. (2)使p2移动n-1个位置,使之指向从头开始的第n个节点.(意思是就是使p1和p2距离n个位置) (3)接下来检查p2 - > = = null 如果yes返回p1的值,否则继续移动p1和 p

算法-C++对输入的文件的数据求一阶倒数

问题描述 C++对输入的文件的数据求一阶倒数 MFC对输入的文件的数据求一阶倒数,然后判定其中的拐点和鞍点的算法是什么? 解决方案 http://download.csdn.net/detail/loveinter1988/4328056

深入线性时间复杂度求数组中第K大数的方法详解_C 语言

求数组中第K大的数可以基于快排序思想,步骤如下:1.随机选择一个支点2.将比支点大的数,放到数组左边:将比支点小的数放到数组右边:将支点放到中间(属于左部分)3.设左部分的长度为L,当K < L时,递归地在左部分找第K大的数当K > L时,递归地在有部分中找第(K - L)大的数当K = L时,返回左右两部分的分割点(即原来的支点),就是要求的第K大的数以上思想的代码实现如下: 复制代码 代码如下: /**线性时间复杂度求数组中第K大数** author :liuzhiwei ** data