链表#

203. 移除链表元素

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

---

示例 1：

1
输入：head = [3,2,0,-4], pos = 1
2
输出：返回索引为 1 的链表节点
3
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

1
输入：head = [1,2], pos = 0
2
输出：返回索引为 0 的链表节点
3
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

1
输入：head = [1], pos = -1
2
输出：返回 null
3
解释：链表中没有环。

---

自己的解法(哈希)

手撕，暴力法哈哈

1
/**
2
 * Definition for singly-linked list.
3
 * type ListNode struct {
4
 *     Val int
5
 *     Next *ListNode
6
 * }
7
 */
8
func detectCycle(head *ListNode) *ListNode {
9
    cur := head
10
    res := make(map[*ListNode]int)
11

12
    for cur != nil {
13
        if res[cur] == 1 {
14
            return cur
15
        }
16
        res[cur]++
17
        cur = cur.Next
18
    }
19

20
    return nil
21
}

快慢指针

第一个想出来快慢指针的人，简直就是天才，太神奇了

思路：快慢指针必然在环内的某一点相遇。我们把整段路程切成三段：

• x：从链表头到环入口的距离。
• y：从环入口到相遇点的距离。
• z：从相遇点继续走，回到环入口的距离

1. 首先，我们要先知道慢指针在进入环之后，绝对不可能走完一整圈，它必定会在第一圈内就被快指针追上。fast和slow的相对速度是1，最大距离是L-1，所以相遇时慢指针移动L-1，L-1 < L，慢指针走过的距离也严格小于环的总长度。

2. 我们可以得出 慢指针距离：x + y，快指针距离：x + y + n(y + z) 或 2(x + y)

3. 2(x + y) = x + y + n(y + z) 得到 x = n(y + z) - y

4. 化简一下 x = (n - 1)(y + z) + z，即他们相遇的点就是我们所求的答案

1
func detectCycle(head *ListNode) *ListNode {
2
    slow, fast := head, head
3

4
    for fast != nil && fast.Next != nil {
5
        fast = fast.Next.Next
6
        slow = slow.Next
7

8
        if slow == fast {
9
            left := head
10
            right := slow
11

12
            for left != right {
13
                left = left.Next
14
                right = right.Next
15
            }
16

17
            return left
18
        }
19
    }
20
    return nil
21
}