leetcode 链接：环路检测
《程序员面试代码指南》by 左程云 中相似题目：★★★★两个单链表相交的一系列问题

题目

给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。

有环链表的定义：在链表中某个节点的 next 元素指向在它前面出现过的节点，则表明该链表存在环路

示例 1：
[中等] 2.8 环路检测 - 图1

  1. 输入：head = [3,2,0,-4], pos = 1
  2. 输出：tail connects to node index 1
  3. 解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：
[中等] 2.8 环路检测 - 图2

输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：
[中等] 2.8 环路检测 - 图3

输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。

解答 & 代码

算法流程：

  • 如果链表为空 或 只有一个节点且该节点的 next 指向 NULL，则链表无环，直接返回 NULL
  • 设置一个快指针和一个慢指针。初始慢指针指向第一个节点，快指针指向第二个节点。遍历链表
    • 慢指针一次走一步，快指针一次走两步
    • 如果链表无环，则快指针的 next 或 next->next 最终会指向 nullptr，退出循环，返回 NULL，代表无环
    • 如果链表有环，则快指针和慢指针会相遇，退出循环
  • 令快指针回到头节点，接着快慢指针都一次走一步，两者再次相遇的节点就是入环节点

理论解释：
image.png

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == NULL || head->next == NULL)
            return NULL;

        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* fast = dummyHead->next->next;
        ListNode* slow = dummyHead->next;
        while(fast != slow && fast->next != NULL && fast->next->next != NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
        }

        if(fast != slow)
            return NULL;

        fast = dummyHead;
        while(fast != slow)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

执行结果：

执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了 91.87% 的用户
内存消耗：7.4 MB, 在所有 C++ 提交中击败了 78.03% 的用户