LeetCode|LeetCode 剑指 Offer 22. 链表中倒数第k个节点 LeetCode剑指Offer22.链表中倒数第

剑指 Offer 22. 链表中倒数第k个节点题意

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

? 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6，则这个链表的倒数第 3 个节点是值为 4 的节点。
? 链表节点的定义如下：

struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(NULL) {} };

方法一：顺序查找
思路 ? 假设该链表含 n 个节点，那么倒数第 k 个节点即为正数的第 n-k+1 个节点。

LeetCode|LeetCode 剑指 Offer 22. 链表中倒数第k个节点

文章图片
算法流程

首先遍历一遍链表，求出链表的长度 n
从第一个节点开始向后移动 n-k 次既是所求答案

Q：为什么是向后移动 n-k 次而不是 n-k+1 次？
A：因为该链表不含头结点且从1开始计数

复杂度分析 ? 时间复杂度：\(O(n)\)
? 空间复杂度：\(O(1)\)
代码

ListNode* getKthFromEnd(ListNode* head, int k) { int n = 0; auto p = head; for (; p != NULL; p = p->next, n++); //遍历求解链表长度 p = head; for (int i = 1; i <= n - k && p != NULL; i++, p = p->next); //向后移动 n-k 个位置 return p; }

方法二：双指针
思路 【LeetCode|LeetCode 剑指 Offer 22. 链表中倒数第k个节点】? 快慢指针思想：

定义两个指针 p , q，将 p 指针指向链表的第 k 个节点，q 指针指向链表的第 1 个节点。
然后让 p,q 指针同步向后走，当 p 指针来到链表尾部时（倒数第一个节点），q 指针刚好指向链表的倒数第 k 个节点

文章图片
复杂度分析 ? 时间复杂度：\(O(n)\)
? 空间复杂度：\(O(1)\)
代码

ListNode* getKthFromEnd(ListNode* head, int k) { auto p = head; auto q = head; for (int i = 1; i < k && p != NULL; i++, p = p->next); //p先行k-1步来到第k个节点 if (p == NULL) return NULL; for (; p->next != NULL; p = p->next, q = q->next); //携手前行，直到p来到链表尾 return q; }

? 方法二相较于方法一，少遍历了一遍，理论上肯定比方法一要快，但是：