力扣打卡：142. 环形链表 II | 快慢指针 | 双指针

题目

142. 环形链表 II

解题思路

链表中与位置有关的计算都可以考虑使用快慢指针，左右指针，如倒数第N个节点，删除倒数第N个节点，中间节点等

• 通过快慢指针确定是否有环
• 通过巧妙地技巧确定slow的k和fast的2k，以及两者首次相遇位置的关系，最后确定链表的环的起始位置

代码

TypeScript

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

// 通过快慢指针测试是否有环，通过一个巧妙地转换k和2k，以及相遇点的关系，即可推算出环起始点的位置
function detectCycle(head: ListNode | null): ListNode | null {
    if (head === null) return null;

    let dummy = new ListNode(-1);
    let fast = dummy, slow = dummy;
    dummy.next = head;

    while (fast !== null && fast.next !== null) {
        fast = fast.next.next;
        slow = slow.next;
        if(fast !== null && fast === slow) break;
    }
    if (fast === null || fast.next === null) return null; // 如果出现非环的情况发，返回null，放到循环外可以减少判断次数

    // 此时可以明确是有环的情况
    fast = dummy;
    while (fast !== slow) {
        fast = fast.next;
        slow = slow.next;
    }
    return fast;
};
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