【一刷《剑指Offer》】面试题 15：链表中倒数第 k 个结点

力扣对应题目链接：LCR 140. 训练计划 II - 力扣（LeetCode）

核心考点 ：链表，前后指针的使用，边界条件检测。

一、《剑指Offer》内容

二、分析问题

较优解题思路：

题目中的链表是单链表，也就不能从后往前进行。
可以定义两个指针（快慢双指针），fast 指针先走 k 步，再让 slow 指针跟在后面，使用 “前后指针” 的方式，当 fast 指针到达结尾，slow 指针也就是倒数第 k 个节点。（其实原理就是：fast 指针和 slow 指针之间一直保持着 k 的距离）

三、代码

//力扣AC代码
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* trainingPlan(ListNode* head, int cnt) {
        ListNode* fast=head;
        ListNode* slow=head;
        while(cnt>0 && fast!=nullptr)
        {
            fast=fast->next;
            cnt--;
        }
        while(fast!=nullptr)
        {
            fast=fast->next;
            slow=slow->next;
        }
        return slow;
    }
};

//严谨写法
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* trainingPlan(ListNode* head, int cnt) {
        if(head==nullptr || cnt<0) return head;
        ListNode* fast=head;
        ListNode* slow=head;
        while(cnt>0 && fast!=nullptr)
        {
            fast=fast->next;
            cnt--;
        }
        while(fast!=nullptr)
        {
            fast=fast->next;
            slow=slow->next;
        }
        if(cnt>0) return nullptr;
        else return slow;
    }
};

四、扩展

力扣对应题目链接：876. 链表的中间结点 - 力扣（LeetCode）

1、分析题目

如果链表中结点总数为奇数，返回中间结点。
如果结点总数是偶数，返回中间两个结点的任意一个。

为了解决这个问题，我们也可以向上面那道题一样定义一个 fast 和 slow 指针，同时从链表的头结点出发，slow 指针一次走一步，fast 指针一次走两步。当 fast 指针走到链表的末尾时，slow 指针正好在链表的中间。

2、代码

//力扣AC代码
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow=head;
        ListNode* fast=head;
        while(fast && fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }
};

力扣对应题目链接：141. 环形链表 - 力扣（LeetCode）

1、分析题目

这道题也一样，定义两个指针 fast 和 slow，同时从链表的头结点出发，slow 指针一次走一步，fast 指针一次走两步。

如果 fast 指针追上了 slow 指针，那么链表就是环形链表。
如果 fast 的指针走到了链表的末尾（m_pNext 指向 NULL）都没有追上 slow 指针，那么链表就不是环形链表。

2、代码

（1）写法一（推荐）

//力扣AC代码
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow=head;
        ListNode* fast=head;
        while(fast && fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
            if(fast==slow) return true;
        }
        return false;
    }
};

（2）写法二

//力扣AC代码
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==NULL || head->next==NULL) return false;
        ListNode* slow=head;
        ListNode* fast=head->next;
        while(fast!=slow)
        {
            if(fast==NULL || fast->next==NULL) return false;
            slow=slow->next;
            fast=fast->next->next;
        }
        return true;
    }
};