47 带环链表II（Linked List Cycle II）_C

文章目录

- 1 题目
- 2 解决方案
- - 2.1 思路
  - 2.2 时间复杂度
  - 2.3 空间复杂度
- 3 源码

1 题目

题目：带环链表II（Linked List Cycle II）
描述：给定一个链表，如果链表中存在环，则返回到链表中环的起始节点，如果没有环，返回null。

lintcode题号——103，难度——hard

样例1：

输入：null，no cycle
输出：no cycle
解释：链表为空，所以没有环存在。

样例2：

输入：-21->10->4->5，tail connects to node index 1
输出：10
解释：最后一个节点5指向下标为1的节点，也就是10，所以环的入口为10。

2 解决方案 2.1 思路

寻找带环链表中环的起点，按照带环链表的第一题¹的思路，使用快、慢指针先判断出链表是否带环，再快慢指针相遇时，在链表头新建一个新的慢指针，新的慢指针与原来的慢指针一起移动，当它们相遇时所在的位置即为环的起点。

该方法是被数学验证过的，放心使用即可，需要深究的同学可以网上搜索看看。

2.2 时间复杂度

时间复杂度为O(n)。

2.3 空间复杂度

空间复杂度为O(1)。

3 源码

细节：

使用快、指针确定链表是否带环。
在快、慢指针相遇时，在链表头处新建一个新的慢指针，两个慢指针一起移动，相遇的位置即是环的起点。

C++版本：

/**
* Definition of singly-linked-list:
* class ListNode {
* public:
*     int val;
*     ListNode *next;
*     ListNode(int val) {
*        this->val = val;
*        this->next = NULL;
*     }
* }
*/
/**
* @param head: The first node of linked list.
* @return: The node where the cycle begins. if there is no cycle, return null
*/
ListNode * detectCycle(ListNode * head) {
    // write your code here
    if (head == nullptr)
    {
        return head;
    }

    ListNode * slow = head;
    ListNode * fast = head;
    while (fast != nullptr && fast->next != nullptr)
    {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) // 如果有环，slow记录了快慢指针相遇的位置
        {
            ListNode * index = head; // 新建一个从头开始的指针
            while (index != slow) // index与slow同时前进，相遇的时候就是链表环的起点
            {
                index = index->next;
                slow = slow->next;
            }

            return index; 
        }
    }

    return nullptr; // 如果无环，则返回空
}