题目描述

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

接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
      
    }
};

解答

使用 stl::map

map<ListNode*, int> 将 ListNode* 与 ListNode* 出现的次数进行对应，如果单链表中不存在环则，则遍历到尾结点的 next 指向的 nullptr 时就会结束遍历，返回 nullptr；而如果单链表中存在环，第一个出现次数大于 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
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    // method via stl::map
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if (pHead == nullptr) return nullptr;
        map<ListNode*, int> lmap;
      	ListNode *node = pHead;
        while (node != nullptr) {
            if (lmap.count(node) > 0) break;
            else (lmap[node] = 1);
            node = node->next;
        }
        return node;
    }
};

使用 stl::set

与使用 stl::map 的思路相似，故不再叙述。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    // method via stl::set
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if (pHead == nullptr) return nullptr;
        set<ListNode*> nodeset;
        while (pHead != nullptr) {
            if (nodeset.count(pHead) > 0) return pHead;
            nodeset.insert(pHead);
            pHead = pHead->next;
        }
        return nullptr;
    }
};

使用快慢指针

设定两个指针，一个慢指针，一个快指针，慢指针一次走的距离是一个结点，而快指针一次走的距离是两个结点，即快指针的速度是慢指针的两倍。

此时，会出现两种情况：

  • 单链表中不存在环则：快指针往后遍历的过程中，会遍历到 nullptr 结点，即单链表中不存在环，最后一个结点指向的是 nullptr。

  • 单链表中存在环则：由于存在环，则快慢指针最后都会进入环中并在环中一直循环，由于快慢指针存在速度差，只要快慢指针一直在环中循环，最终会在环中的一个结点相遇，相遇时快指针至少在环中循环了一圈。

    • 如果这时快指针已经是在环里走了 1 圈（对应于非环部分较短的情况）：

      此时快指针走了 2(x + d) (0 <= d) 距离，2(x + d) = x + y + d ，可得 x = y - d ，此时再同时从第一次相遇点和头结点出发，速度都为一个结点每次，最后两指针会在环入口结点处相遇。

    • 如果这时快指针已经是在环里走了不止一圈，假设为 k 圈：

      此时快指针走了 2(x + d) (0 <= d)​ 距离，2(x + d) = x +ky + d​，可得 x = ky - d​ ，此时再同时从第一次相遇点和头结点出发，速度都为一个结点每次，最后两指针也会在环入口结点处相遇。

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
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    // method via fast pointer and slow pointer
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
      	if (pHead == nullptr) return nullptr;
      	ListNode *slow = pHead, *fast = pHead;
      	do {
            if (fast->next != nullptr && fast->next->next != nullptr) {
                slow = slow->next;
                fast = fast->next->next;
            } else {
                return nullptr;
            }
      	} while (slow != fast);
      	fast = pHead;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    }
};

详细思路参考：一个链表中包含环，请找出该链表的环的入口结点