秋高斋

142. 环形链表 II

发表于 更新于 分类于
本文字数： 1.3k 阅读时长 ≈ 2 分钟
三种办法解题

142. 环形链表 II

这道题非常地有趣，旨在找到链表中环的起始点。

哈希法

最容易的办法是遍历链表中的每个节点，用哈希表储存地址，如果有重复的内容，说明找到了环的起始点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode *> visited;
        while(head != nullptr)
        {
            if(visited.count(head)) //返回head出现的次数
            {
                return head;
            }
            visited.insert(head);
            head = head->next;
        }
        return nullptr;
        }
};

数学法

第二种办法是数学法，具体可以参考题解：环形链表 II（双指针法，清晰图解）

概括一下：

根据：

f = 2s （快指针每次2步，路程刚好2倍）

f = s + nb （相遇时，刚好多走了n圈）

推出：s = nb

从head结点走到入环点需要走 ： a + nb， 而slow已经走了nb，那么slow再走a步就是入环点了。

如何知道slow刚好走了a步？ 从head开始，和slow指针一起走，相遇时刚好就是a步.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
         ListNode* fast = head;
         ListNode* slow = head;
        while (true) {
            if (fast == NULL || fast->next == NULL) return NULL;
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) break;
        }
        fast = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    }
};

巧妙法

O(n)算法，应该是最快的。 堆的地址从低到高，LeetCode的链表内存是顺序申请的，如果有环，head->next一定小于或等于head。

这个办法在实际生产中没法使用，因为堆内会不断地new和delete新的节点。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        while(head) {
            if(!less<ListNode *>()(head, head->next)) {
                return head->next;
            }
            head = head->next;
        }
        return nullptr;
    }
};