摘要：导航小助手剑指链表中倒数第个节点题目详情解题思路源代码总结剑指链表中倒数第个节点题目详情输入一个链表，输出该链表中倒数第个节点。为了符合大多数人的习惯，本题从开始计数，即链表的尾节点是倒数第个节点。这个链表的倒数第个节点是值为的节点。
⭐️前面的话⭐️
大家好！博主开辟了一个新的专栏——剑指offer，我要开始刷题了！这个专栏会介绍《剑指offer》书上所有的面试编程题。并且会分享一些我的刷题心得。由于博主水平有限，如有错误，欢迎指正，如果有更好的解题思路和算法可以分享给博主哦！一起加油！一起努力！
?博客主页：未见花闻的博客主页
?欢迎关注?点赞?收藏⭐️留言?
?本文由未见花闻原创，CSDN首发！
?首发时间：?2021年9月12日?
✉️坚持和努力一定能换来诗与远方！
?参考书籍：?《剑指offer第1版》，?《剑指offer第2版》
?参考在线编程网站：?牛客网?力扣
?作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！
博主的码云gitee，平常博主写的程序代码都在里面。
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.返回链表 4->5.限制：
无来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
方法1： 遍历。
最直接的方法就是遍历链表，第一次遍历链表求出链表元素个数len，得到链表元素个数后，倒数第k个结点即第len - k + 1个结点，如果从0开始数就是第len - k个结点，所以第二次遍历目的是找到这个结点并返回这个结点的地址，遍历次数为len - k + 1。
时间复杂度： O(N)
方法2： 快慢指针。
我们都知道公交车每班车次的发出都会间隔一段时间，假设每班公交车从起点站到终点站所用时间相同，那么在这种理想情况下每相邻两班公交车到终点站的时间差即为每相邻两班发车的时间差。我们可以根据这种快慢的差异思想来思考这道题，我们需要求倒数第k个结点，我们可以让一个快指针fast先走k步，然后再让一个慢指针slow出发，fast走一步slow也走一步，等到fast走到终点时，slow刚好走到fast前面k步的位置，也就是倒数第k个结点。
时间复杂度： O(N)
编程语言：C语言
在线编程平台：力扣
//方法1：struct ListNode* getKthFromEnd(struct ListNode* head, int k){ if(!head) return NULL; int size = 0; struct ListNode* cur = NULL; cur = head; while (cur) { size++; cur = cur->next; } int i = 0; cur = head; for (i = 0; i < size - k; i++) { cur = cur->next; } return cur;}//方法2：struct ListNode* getKthFromEnd(struct ListNode* head, int k){ if (head == NULL) { return NULL; } struct ListNode* fast = head; struct ListNode* slow = head; int i = 0; for(i = 0; i < k && fast; i++) { fast = fast->next; } while (fast) { slow = slow->next; fast = fast->next; } return slow;}求单链表倒数第k个结点，最简单直接的方法就是遍历求出链表长度然后根据链表长度找到目的结点的位置。更深一步，我们可以参考公交车发车的思想，根据遍历的结点差使用快慢指针得到倒数第k个结点。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/119942.html
摘要：题目输入一个链表，输出该链表中倒数第个结点。思路简单思路循环到链表末尾找到在找到节点需要循环两次。优化设定两个节点，间距相差个节点，当前面的节点到达终点，取后面的节点。本题目着重考察代码鲁棒性容错率需要考虑为，为，大于链表长度的情况代码 题目 输入一个链表，输出该链表中倒数第k个结点。 思路 showImg(https://segmentfault.com/img/remote/146...
摘要：剑指中链表相关题目俗话说光说不练假把式，既然学习了链表的基础概念和基本操作那我们一定要找些题目巩固下，下面来看剑指中的相关题目。题目分析合并两个排序的链表，需要分别比较两个链表的每个值，然后改变指针。 温故知新 链表由一个一个的作为节点的对象构成的，每一个节点都有指向下一个节点的指针，最后一个节点的指针域指向空。每个节点可以存储任何数据类型。 根据类型可以分为单链表、双链表、环形链表、...
摘要：导航小助手剑指删除链表的节点题目详情解题思路源代码总结剑指删除链表的节点题目详情给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。 ...
摘要：导航小助手剑指从尾到头打印链表题目详情解题思路源代码总结剑指从尾到头打印链表题目详情输入一个链表的头节点，从尾到头反过来返回每个节点的值用数组返回。时间复杂度方法先反转链表并求长度，在将反转后的链表数据拷贝至数组中。 ...
摘要：说明不允许修改给定的链表。注意，函数返回结果后，链表必须保持其原始结构。示例输入输出解释相交节点的值为注意，如果两个链表相交则不能为。将这两数相加会返回一个新的链表。 ...
阅读 746·2021-09-22 15:26
阅读 2078·2021-09-14 17:57
阅读 2335·2021-09-09 11:52
阅读 1596·2021-09-02 09:52
阅读 2074·2021-08-12 13:28
阅读 1053·2019-08-30 15:53
阅读 359·2019-08-29 13:47
阅读 3250·2019-08-29 11:00
