Leetcode-142. 环形链表 II

发表于 分类于 阅读次数：

142. 环形链表 II

解法1：set

用set存走过的节点，若后面走过的点已经在set中直接返回该节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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 *> s;
        while(head!=NULL)
        {
            if(s.find(head)!=s.end())
                return head;
            s.insert(head);
            head=head->next;
        }
        return NULL;
    }
};
解法2：Floyd算法

阶段1：

一个指针每次走两步，一个每次走一步，若两指针在某时刻相同，表示有环，且记录该节点位置

阶段2：

一个指针从头开始，一个从刚才记录位置开始，当两指针相遇就找到了入环的第一个节点

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) {
        ListNode *p=head;
        ListNode *ph=head;
        ListNode *f;
        int flag=0;
        while(p&&p->next)
        {
            p=p->next->next;
            ph=ph->next;
            if(ph==p)
            {
                flag=1;
                f=ph;
                break;
            }
        }
        if(!flag)  return NULL;
        p=head;
        while(p!=f)
        {
            p=p->next;
            f=f->next;
        }
        return f;
    }
};