LeetCode 劍指 Offer 22. 鏈表中倒數第k個節點
劍指 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 個節點。
算法流程
- 首先遍歷一遍鏈表，求出鏈表的長度 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;
}
方法二：雙指針
思路
快慢指針思想：
- 定義兩個指針 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;
}
方法二相較於方法一，少遍歷了一遍，理論上肯定比方法一要快，但是：
方法一：順序查找
方法二：雙指針
不能理解 😕
