剑指offer----C语言版----第十六天----面试题22：链表中的倒数第k个节点

姬如祎

735人浏览 · 2023-01-12 07:00:00

姬如祎 · 2023-01-12 07:00:00 发布

1. 链表中倒数第 k 个节点

原题链接：

剑指 Offer 22. 链表中倒数第k个节点 - 力扣（LeetCode）https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

1.1 题目描述

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

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

1.2 思路一

题目求的是链表的倒数第 k 个节点，根据题目得知这是一个单向链表，我们无法从后往前找到链表的倒数第 k 个节点，于是我们会想到从前往后去找倒数第 k 个节点。但是我们不知道倒数第 k 个节点前面有多少个节点。于是，我们很自然地想到先求出链表的节点个数 count，然后就求出了倒数第 k 个节点前有 count - k 个节点，然后我们再用一个指针去遍历找到倒数第 k 个节点就可以啦。

struct ListNode* getKthFromEnd(struct ListNode* head, int k) {
    //对输入进行判断，提高代码的鲁棒性(健壮性)
    if (head == NULL || k <= 0)
    {
        return NULL;
    }
    //用cur指针遍历链表统计节点个数
    struct ListNode* cur = head;
    int count = 0;
    while (cur != NULL)
    {
        count++;
        cur = cur->next;
    }
    //对输入进行判断，提高代码的鲁棒性    
    if (k > count)
    {
        return NULL;
    }
    //找到倒数第k个节点
    struct ListNode* ret = head;
    int i;
    for (i = 1; i < count - k + 1; i++)
    {
        ret = ret->next;
    }
    return ret;
}

1.3 思路二：

遍历两次链表还是太麻烦了，能不能只遍历一次链表就找到结果呢？答案是肯定的，我们可以维护两个指针slow，fast，将他们均初始化为头结点 head。然后让 slow 指针先不动，让 fast 指针先向后走k-1步，此时slow与fast之间就隔了 k - 1 个节点，然后保持slow与fast之间的距离始终为 k - 1个节点，即之后让 slow 与 fast 同时向后移动。直到 fast 指向尾节点，此时 slow 就指向了链表的倒数第 k 个节点。

下面以链表 1->2->3->4->5->NULL ，k = 3，举例分析：

struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    //对输入进行判断，提高代码的鲁棒性(健壮性)
    if(head == NULL && k <= 0)
    {
        return NULL;
    }
    //两个指针的初始化
    struct ListNode* slow = head, *fast = head;
    //快指针先走走k-1步，此情况中可能超过快指针可走的步数，
    //此时表明链表的节点个数小于k的值，返回NULL
    int i = 0;
    for(i = 0;i < k - 1;i++)
    {
        if(fast != NULL)
            fast = fast->next;
        else
            return NULL;
    }
    //让慢指针与快指针同时走，直到快指针走到尾节点
    //最后慢指针指向的节点就是倒数第k个节点
    while(fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}