Fork me on GitHub

剑指Offer之链表中环的入口结点

发表于 | 分类于
字数统计 351 字 | 阅读时长 1 分钟

题目描述：

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

解题思路：

两个指针一个fast、一个slow同时从一个链表的头部出发, fast一次走2步，slow一次走一步，如果该链表有环，两个指针必然在环内相遇,此时只需要把其中的一个指针重新指向链表头部，另一个不变（还在环内），这次两个指针一次走一步，相遇的地方就是入口节点。

时间复杂度：$O(n^2)$, 空间复杂度：$O(1)$.

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
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        ListNode* p = pHead;
        ListNode* q = pHead;
        if(pHead == NULL)
            return NULL;
        while(q->next != NULL && q->next->next != NULL){
            p = p->next;
            q = q->next->next;
            if(p == q)
            {
                q = pHead;
                while(p != q)
                {
                    p = p->next;
                    q = q->next;
                }
                return p;
            }
        }
        return NULL;
    }
};

时间复杂度：$O(n^2)$, 空间复杂度：$O(1)$.

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
37
38
39
40
41
42
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if (!pHead || pHead->next == NULL) return NULL;
        
        ListNode *h1 = pHead;
        ListNode *h2 = pHead;
        ListNode *h3 = pHead;
        int flag = 0;
        
        while(h2)
        {
            h1 = h1->next;
            h2 = h2->next->next;
            if(h1 == h2)
            {
                flag = 1;
                break;
            }
        }
        while(flag)
        {
            if(h1 == h3)
                return h1;
            h1 = h1->next;
            h3 = h3->next;
         }
        
        return NULL;

    }
};