剑指offer | 22.链表中倒数第k个节点-蒲公英云

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

r囧r小猫 2022-12-27 02:27 233阅读 0赞

题目内容：

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

思路

我一开始想的是链表没办法统计链表的大小所以可以先遍历统计一遍链表结点的个数n，然后从前往后找到第n-k+1个节点就是题目所要求的倒数第k个结点，emmm但是还是代码水平烂，我编不出ac的代码，所以看了大佬的题解。
看完，直拍大腿，妙啊！用双指针就解决了。你只要让其中一个指针往后走k步，然后两个指针再同时移动直到后面的指针到底了，那么前一个指针指向的就是倒数第k个结点。

代码

class Solution { 
public:
    ListNode* getKthFromEnd(ListNode* head, int k) { 
        ListNode *p = head, *q = head; //初始化
        while(k--) {    //将 p指针移动 k 次
            p = p->next;
        }
        while(p != nullptr) { //同时移动，直到 p == nullptr
            p = p->next;
            q = q->next;
        }
        return q;
    }
};

参考：一文搞定常见的链表问题 (欢迎交流（这个题解写得太妙了，基本总结了所有链表可能的考题！）

同样的，那么针对链表问题的其他相关面试题也摘抄一下：

获取中间元素的问题。 设有两个指针 fast 和 slow，初始时指向头节点。每次移动时，fast向后走两次，slow向后走一次，直到 fast 无法向后走两次。这使得在每轮移动之后。fast 和 slow 的距离就会增加一。设链表有 n 个元素，那么最多移动 n/2 轮。当 n 为奇数时，slow 恰好指向中间结点，当 n 为偶数时，slow 恰好指向中间两个结点的靠前一个

class Solution {
public:
```
ListNode* middleNode(ListNode* head) { 
    ListNode *p = head, *q = head;
    while(q != nullptr && q->next != nullptr) { 
        p = p->next;
        q = q->next->next;
    }
    return p;
} 
```
};
是否存在环的问题。 当一个链表有环时，快慢指针都会陷入环中进行无限次移动，然后变成了追及问题。想象一下在操场跑步的场景，只要一直跑下去，快的总会追上慢的。当两个指针都进入环后，每轮移动使得慢指针到快指针的距离增加一，同时快指针到慢指针的距离也减少一，只要一直移动下去，快指针总会追上慢指针。

class Solution {
public:
```
bool hasCycle(ListNode *head) { 
    ListNode *slow = head;
    ListNode *fast = head;
    while(fast != nullptr) { 
        fast = fast->next;
        if(fast != nullptr) { 
            fast = fast->next;
        }
        if(fast == slow) { 
            return true;
        }
        slow = slow->next;
    }
    return nullptr;
}
```
};