142. 环形链表 II#

题目#

1
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
2

3
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
4

5
如果 pos 是 -1，则在该链表中没有环。
6

7
注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
8

9
说明：不允许修改给定的链表。
10

11
进阶：
12

13
你是否可以使用 O(1) 空间解决此题？
14

15
示例 1：
16

17
输入：head = [3,2,0,-4], pos = 1
18
输出：返回索引为 1 的链表节点
19
解释：链表中有一个环，其尾部连接到第二个节点。
20

21
示例 2：
22

23
输入：head = [1,2], pos = 0
24
输出：返回索引为 0 的链表节点
25
解释：链表中有一个环，其尾部连接到第一个节点。
26

27
示例 3：
28

29
输入：head = [1], pos = -1
30
输出：返回 null
31
解释：链表中没有环。
32

33
提示：
34

35
链表中节点的数目范围在范围 [0, 10^4] 内
36
-10^5 <= Node.val <= 10^5
37
pos 的值为 -1 或者链表中的一个有效索引

题目思路#

经典双指针问题，同时与昨日的题目一样，也可以使用哈希表解法，但哈希表的空间复杂度较高，效果不佳；
双指针解法的完整证明见官方题解，此处不再赘述。

题目代码#

代码块#

1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode(int x) : val(x), next(NULL) {}
7
 * };
8
 */
9
class Solution {
10
public:
11
    ListNode *detectCycle(ListNode *head) {
12
        if(head == NULL || head -> next == nullptr) return NULL;
13
        ListNode* fast = head;
14
        ListNode* slow = head;
15
        while(fast != nullptr && fast -> next != nullptr)
16
        {
17
            slow = slow -> next;
18
            fast = fast -> next -> next;
19
            if(fast == slow)
20
            {
21
                ListNode* tmp = head;
22
                while(tmp != slow)
23
                {
24
                    tmp = tmp -> next;
25
                    slow = slow -> next;
26
                }
27
                return tmp;
28
            }
29
        }
30
        return NULL;
31
    }
32
        /* if(head == NULL || head -> next == nullptr) return NULL;
33
        unordered_set<ListNode* > m;
34
        ListNode* fast = head;
35
        while(fast -> next != nullptr)
36
        {
37
            if(m.count(fast) != 0) return fast;
38
            m.insert(fast);
39
            fast = fast -> next;
40
        }
41
        return nullptr; */
42
    }
43
};

复杂度#

时间复杂度：双指针 O(n)，哈希表为 O(n)；
空间复杂度：双指针 O(1)，哈希表为 O(n)。