链表¶

虚拟头结点¶

当头结点会变时，可以简化代码

ListNode dummy{ 0,head };
ListNode* prev = &dummy;
ListNode* curr = head;

双指针。第一个指针先遍历 A 再遍历 B，第二个指针先遍历 B 再遍历 A，相遇时，如果是 nullptr 则没相交，否则就是交点（c1）。

快慢指针。快指针先走 k 步，然后慢指针和快指针一起走，快指针走到底时，慢指针所在的就是倒数第 k 个。

快慢指针。快指针一次走两步，慢指针一次走一步，快指针走到底时，慢指针所在的就是中点。

快慢指针。快指针一次走两步，慢指针一次走一步，两指针一定会在环中相交（假设是紫色的点）。快指针走了 \(a+b+k(b+c)\)，慢指针走了 \(a+b\)，而快指针走的距离一定是慢指针的两倍，所以

\[ a+b+k(b+c)=2(a+b) \Rightarrow a=(k-1)(b+c)+c \]

可以发现，\(a\) 的长度就等于，在环中绕 \(k-1\) 圈再加 \(c\) 的长度。因此，当快慢指针相遇后，让慢指针继续向前，再让另一个指针从头结点开始一次一步向前，两者相遇的地方就是环的起点。