输出链表的倒数第k个结点（C++）

刷题平台

牛客网

题目

输入一个链表，输出链表中倒数第k个结点。

解题思路

假设两个指针p1，p2，两个指针都指向链表的头指针。

p1指针依次遍历链表，直到移动到第 k 个结点时，p2指针开始从表头开始遍历。

p1和p2两指针继续同时往后遍历（p1和p2两指针的间隔是固定的），直到p1指针指向边表末尾时，p2指针指向的结点就是链表中倒数第 k 个结点。

以下链表输出倒数第2个结点，

p1指针指向第2个结点，p2指针指向第1个结点。

p1和p2指针同时向后遍历，直到链表末尾。

p2指针指向的结点就是要输出的倒数第 2 个结点。

代码

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

class Solution
{
public:
    ListNode *FindKthToTail(ListNode *pListHead, int k)
    {
        if (pListHead == NULL || k == 0) // 链表为空或要求输出的结点位置不合法
            return NULL;
        ListNode *p1 = pListHead;
        ListNode *p2 = pListHead;
        for (int i = 0; i < k-1; i++) // 得到p1指向第 k 个结点的指针
        {
            if (p1->next != NULL)
                p1 = p1->next;
            else
                return NULL;
        }
        while (p1->next != NULL) // p1,p2指针同时向后遍历
        {
            p1 = p1->next;
            p2 = p2->next;
        }
        return p2;
    }
};

---

参考博文链接：https://cuijiahua.com/blog/2017/12/basis_14.html