摘要：如果鏈表無(wú)環(huán)，則返回。說(shuō)明不允許修改給定的鏈表。示例輸入輸出解釋鏈表中有一個(gè)環(huán)，其尾部連接到第一個(gè)節(jié)點(diǎn)。兩種方法哈希表哈希表添加節(jié)點(diǎn)時(shí)只要發(fā)現(xiàn)節(jié)點(diǎn)已經(jīng)存在了，證明就有環(huán)形鏈表。

給定一個(gè)鏈表，返回鏈表開(kāi)始入環(huán)的第一個(gè)節(jié)點(diǎn)。 如果鏈表無(wú)環(huán)，則返回 null。

為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來(lái)表示鏈表尾連接到鏈表中的位置（索引從 0 開(kāi)始）。 如果 pos 是 -1，則在該鏈表中沒(méi)有環(huán)。

說(shuō)明：不允許修改給定的鏈表。

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：tail connects to node index 1
解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第二個(gè)節(jié)點(diǎn)。

示例 2：

輸入：head = [1,2], pos = 0
輸出：tail connects to node index 0
解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第一個(gè)節(jié)點(diǎn)。

示例 3：

輸入：head = [1], pos = -1
輸出：no cycle
解釋：鏈表中沒(méi)有環(huán)。

進(jìn)階： 你是否可以不用額外空間解決此題？

Follow-up: Can you solve it without using extra space?

和上一道題比只多了一步判斷入環(huán)節(jié)點(diǎn)在哪。兩種方法：

哈希表：

哈希表添加節(jié)點(diǎn)時(shí)只要發(fā)現(xiàn)節(jié)點(diǎn)已經(jīng)存在了，證明就有環(huán)形鏈表。并且已存在的節(jié)點(diǎn)即為入環(huán)節(jié)點(diǎn)

雙指針：

畫了個(gè)圖幫助理解：

一快一慢雙指針開(kāi)始從頭結(jié)點(diǎn)遍歷鏈表，快節(jié)點(diǎn)速度為2，慢節(jié)點(diǎn)速度為1：

相遇時(shí)：

慢節(jié)點(diǎn)走了：a+b

由于快指針?biāo)俣仁锹羔樀?倍，快節(jié)點(diǎn)走了：2(a+b)

快慢節(jié)點(diǎn)相遇時(shí)快節(jié)點(diǎn)比慢節(jié)點(diǎn)剛好多走了一圈環(huán)形節(jié)點(diǎn)。快節(jié)點(diǎn)走了：(a+b)+(b+c)

列方程：2(a+b)=(a+b)+(b+c)

解得 a=c

也就是說(shuō)：相遇節(jié)點(diǎn)到入環(huán)節(jié)點(diǎn)的長(zhǎng)度和頭節(jié)點(diǎn)到入環(huán)節(jié)點(diǎn)的長(zhǎng)度相等

可以得出結(jié)論，如果此時(shí)讓慢節(jié)點(diǎn)或快節(jié)點(diǎn)中的一個(gè)指向頭節(jié)點(diǎn)，另一個(gè)留在相遇節(jié)點(diǎn)，然后速度都為1，繼續(xù)遍歷鏈表，雙指針再次相遇時(shí)的節(jié)點(diǎn)剛好是入環(huán)節(jié)點(diǎn)。

注：為了理解方便，把長(zhǎng)度 b 定為上半部分長(zhǎng)度，實(shí)際上 b 應(yīng)該為快慢節(jié)點(diǎn)相遇時(shí)慢節(jié)點(diǎn)繞過(guò)環(huán)形鏈表的總長(zhǎng)度

Java：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;//如果是空鏈表直接返回
        Set nodeSet = new HashSet<>();//構(gòu)造哈希表
        while (head.next != null) {//鏈表下一個(gè)不為空
            if (nodeSet.contains(head)) return head;//哈希表包含該節(jié)點(diǎn)則存在環(huán)形鏈表
            nodeSet.add(head);//加入節(jié)點(diǎn)
            head = head.next;//下移一位
        }
        return null;
    }
}

Python：

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None:
            return None
        hashSet=set()#構(gòu)造集合
        while(head.next is not None):
            if head in hashSet:#是否已存在
                return head
            hashSet.add(head)
            head=head.next
        return None

Java：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {//快指針及其下一位是否為null
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {//如果相同，存在環(huán)形鏈表
                slow = head;//指向頭節(jié)點(diǎn)
                while (slow != fast) {//繼續(xù)遍歷，再次相遇時(shí)的節(jié)點(diǎn)即為入環(huán)節(jié)點(diǎn)
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }
}

Python：

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return None
        slow, fast = head, head
        while fast is not None and fast.next is not None:
            slow, fast = slow.next, fast.next.next
            if slow == fast:
                slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                return slow
        return None

歡迎關(guān)注公眾號(hào)：愛(ài)寫B(tài)ug（ID：iCodeBugs）