【面试题】剑指offer15--求链表中的倒数第k个结点

骑猪看日落 2022-06-13 00:30 115阅读 0赞

求链表中的倒数第k个结点

从最后一个节点开始计算，最后一个就是1，依次往前加

一种方法是遍历两遍，第一遍计算出总共的结点数，第二遍遍历找出倒数第k个结点

倒数第k个结点就是正数的第n-k+1个结点

另一种方法是定义两个指针，当第一个指针走到第K-1的数时，第二个指针开始走

当第一个指针到最后时，则第二个指着刚好走到倒数第k个结点

代码实现：

#define _CRT_SECURE_NO_DEPRECATE
    #include<iostream>
    using namespace std;
    #include<stack>
    struct  ListNode
    {
    	int value;
    	ListNode* next;
    };
    
    ListNode* FindKthToTail(ListNode* pListHead,unsigned int k)
    {
    	if (pListHead == NULL || k == 0)//当头结点为空或者k等于0时
    	{
    		return NULL;//直接返回
    	}
    	ListNode *pHead1 = pListHead;//定义第一个指针等于头节点
    	ListNode *pHead2 = NULL;//定义第二个指针为空
    	for (unsigned int i = 0; i < k - 1; i++)
    	{
    		if (pHead1->next != NULL)//的一个指针的下一个不为空的时候，向后走，直到k-1的位置
    		{
    			pHead1 = pHead1->next;
    		}
    		else
    		{
    			return NULL;
    		}
    	}
    	//当pHead1走到第k-1位置时，第二个指针开始向后走
    	pHead2 = pListHead;//第二个指针等于头节点
    	while (pHead1->next != NULL)
    	{//两个指针都向后走，第一个指针走到最后时，第二个指针刚好就是倒数第K的节点
    		pHead1 = pHead1->next;
    		pHead2 = pHead2->next;
    	}
    	return pHead2;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，115人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指offer面试题链表中倒数第K个结点

题目描述：输入一个链表，输出该链表中倒数第K个结点。本题从1开始计数，即链表的尾结点是倒数第一个结点。例如一个链表有6个结点，从头开始它们的值依次是1、2、3、4、5、6。

淡淡的烟草味﹌/ 2022年08月21日 06:43/ 0 赞/ 164 阅读

相关剑指offer面试题15（java版）：链表中倒数第k个结点

题目：输入一个链表，输出该链表中倒数第k哥结点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第1个结点。例如一个链表有6个结点，从头结点

港控/mmm°/ 2022年07月16日 04:54/ 0 赞/ 115 阅读

相关剑指offer面试题[15]-链表中倒数第K个结点

题目描述输入一个链表，输出该链表中倒数第k个结点。思路：假设链表有n个结点，那么倒数第k个结点就是从头结点开始的第n-k+1个结点，我们只要从

逃离我推掉我的手/ 2022年06月13日 03:58/ 0 赞/ 120 阅读

相关【面试题】剑指offer15--求链表中的倒数第k个结点

求链表中的倒数第k个结点从最后一个节点开始计算，最后一个就是1，依次往前加一种方法是遍历两遍，第一遍计算出总共的结点数，第二遍遍历找出倒数第k个结点倒数第k个结点就

骑猪看日落/ 2022年06月13日 00:30/ 0 赞/ 116 阅读

相关剑指Offer | 链表中倒数第k个结点

做了个剑指Offer的题目目录，链接如下： [https://blog.csdn.net/mengmengdastyle/article/details/80317246]

古城微笑少年丶/ 2022年05月24日 03:44/ 0 赞/ 195 阅读

相关剑指offer:链表中倒数第k个结点

题目描述输入一个链表，输出该链表中倒数第k个结点。 AC C++ Solution: 使用双指针法,一个指针先移动k-1步, 然后同时移动, 快指针到达链表末尾时,

àì夳堔傛蜴生んèń/ 2022年04月10日 07:54/ 0 赞/ 208 阅读

相关【剑指offer】链表中倒数第k个结点

链表中倒数第k个结点题目描述输入一个链表，输出该链表中倒数第k个结点。解题思路设置两个指针，让其中一个指针比另一个指针先前移k-1步，然后两个指针同

忘是亡心i/ 2022年04月08日 17:11/ 0 赞/ 312 阅读

相关剑指Offer-链表中倒数第k个结点

题目描述输入一个链表，输出该链表中倒数第k个结点。初步解题思路：先求出链表总长，再从头遍历到倒数第k个结点。最优解：这个想法很巧妙。因为求得是倒数第k个，所以

╰半夏微凉°/ 2022年02月28日 13:16/ 0 赞/ 257 阅读

相关剑指offer链表中倒数第k个结点

题目:输入一个链表，输出该链表中倒数第K个节点；为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第一个结点。题目分析： ![在这里插入图

素颜马尾好姑娘i/ 2021年09月19日 18:38/ 0 赞/ 424 阅读

相关剑指offer：链表中倒数第k个结点

试题：输入一个链表，输出该链表中倒数第k个结点。代码：很巧妙的思想，使用一个指针先走k-1步是的p与q相距k个节点。然后两个指针一直往下走，知道探底。 /

我不是女神ヾ/ 2021年06月24日 16:00/ 0 赞/ 389 阅读