思想

双指针算法不仅应用于链表，在数组等数据结构中也有广泛应用。
核心思路是指向问题中的关键节点，根据问题的上下文逻辑变换位置，最终解决问题。

实例

环形链表 II leetcode 142

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

输入：
head: ListNode，一个链表

输出：
ListNode，如果链表中无环返回 None，有环则返回环的开始节点。

举例：
当 head = [3,2,0,-4], [2,0,-4] 成环时，返回环开始的节点 2。

关键点

核心是判断是否有环，并寻找到环开始的位置。
（1）判断环
使用两个指针，快的步长为 2，慢的步长为 1，当快的到达末端前，如果和慢的相遇，存在环。
（2）环开始的位置

head ----> start - \
             /     meet
            |         |
             \       /
               - - -  

slow 和 fast 分别从 head 出发，经过了环开始位置 start，在 meet 处相遇。
此时 slow 行进距离为 head -> start -> meet，fast 形近距离为 head -> start -> meet --[n 圈]--> meet。 设 head -> start = a
，start -> meet = b，环长度 c，fast 在相遇前饶了 n 圈。
slow 距离 = a + b，fast 距离 = a + b + nc。
fast 行进距离是 slow 的 2 倍，a + b + nc = 2(a + b) => a + b = nc => a = nc - b。
如果从 meet 和 head 用相同步速前进，当 head 处前进 a 到达 start 的时候，meet 处前进了 nc - b 也到达了 start，这样就找到了环的起始点。

编码

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def linked_list_cycle_ii(head: ListNode) -> ListNode:
    # 初始位置都在 head
    slow = fast = head
    # fast 步速 2，slow 步速 1，判断是否有环
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        # 存在环，寻找环初始节点
        if slow == fast:
            start = head
            while start != fast:
                start = start.next
                fast = fast.next
            return start
    return None

相关

双指针 0
双指针 1
双指针 2
双指针 3
双指针 4