142. 环形链表 II

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

Solution1:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        std::set<ListNode*> node_set;
        while(head){
            if(node_set.find(head) == node_set.end()){
                node_set.insert(head);
            }else{
                return head;
            }
            head = head->next;
        }
        return NULL;
    }
};

与141号问题的Solutions1一个思路，直接使用set。只不过返回的是结点不是boolean值罢了。

Solutions2:
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
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode * head1 = head;
        ListNode * slow = head;
        ListNode * fast = head;
        //fast走一步，slow走两步
        while(fast){
            slow = slow->next;
            fast = fast->next;
            if(fast){
                fast = fast->next;
            }else{ //没有环退出
                return NULL;
            }
            //有环退出循环
            if(fast == slow){
                break;
            }
        }
        //说明有环
        while(head1 && fast){
            if(head1 == fast){
                return fast;
            }
            head1 = head1->next;
            fast = fast->next;
            
        }
        //不会走到这步，只是为了保证函数正常运行
        return NULL;
    }
};
思路：

这种方法只会使用O(1)的空间。

该方法的思路需要一点数学基础：

在一个有环的链表中，slow指针与fast指针相遇，从该相遇的位置开始，与链表的头位置开始，两者走同样的步数，如果两者相交，就走到了环的开始位置。

image