袋熊的树洞

日拱一卒，功不唐捐

0%

LeetCode 142 - Linked List Cycle II

Posted on Edited on

问题描述

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

1
2
3
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

1
2
3
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Follow-up:

Can you solve it without using extra space?

Related Topics: Linked List, Two Pointers

原问题: 142. Linked List Cycle II

中文翻译版: 142. 环形链表 II

解决方案

解决方案1

用一个 Set 保存已访问的节点，此时可以遍历整个链表并返回第一个出现重复的节点。时间复杂度为 O(n)，空间复杂度为 O(n)

参考解题代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 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) {
        set<ListNode*> node_set;
        ListNode *node;

        node = head;
        while (node != NULL) {
            if (node_set.find(node) == node_set.end())
                node_set.insert(node);
            else
                return node;
            node = node->next;
        }

        return node;
    }
};

解决方案2

方案2是 LeetCode 141 解题思路的进一步改进，算法分为两个阶段：

  • 阶段1 : 首先使用快指针 fast 和慢指针 slow 遍历链表，如果链表有环，两指针最终会相遇到某个节点
  • 阶段2 : 初始化额外的两个指针，ptr1 指向链表的头节点，ptr2 指向相遇节点。然后，我们每次将它们往前移动一步，直到它们相遇，它们相遇的点就是环的入口，返回这个节点

关于阶段2的实现原理，这里提供一个不错的解答说明：LeetCode: 环形链表 II 官方解答

参考解题代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 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 (NULL == head || NULL == head->next)
            return NULL;

        ListNode *slow, *fast;

        slow = fast = head;
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast)
                break;
        }
        // no cycle
        if (slow != fast)
            return NULL;

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

        return fast;
    }
};