计算机科学基础leetcode刷题链表
, ,
Source
Edit
History

142. 环形链表 II

Problem: 142. 环形链表 II

思路

暴力算法超时了,不考虑

主要理解以下公式

vos3a

解题方法

当快指针追上慢指针的时候说明有环,

用以上证明可以得到让一个指针从head出发,一个指针从相遇点出发他们一定在入口相遇,

复杂度

  • 时间复杂度:

$O(n)$

  • 空间复杂度:

$O(1)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head,*slow = head;
        //fast一次两步 slow一次一步
        while(fast!=nullptr&&fast->next!=nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            //找到交点
            if(fast==slow) {
                //一个在头 一个在交点
                ListNode *a = head,*b = fast;
                while(a!=b) {
                    a = a->next;
                    b = b->next;
                }
                return a;
            }
        }
        return nullptr;
    }
};
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

class Solution {

public:

    ListNode *detectCycle(ListNode *head) {

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

            slow = slow->next;

            if(fast == slow) { //有环
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while(index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }
  
        return nullptr;
    }
};