为何双指针算法（快慢指针法）可行？链表找中间节点原理疑问

• 核心前提：快慢指针从链表头部同步出发，快指针每次移动2个节点，慢指针每次移动1个节点，快指针的移动速度是慢指针的2倍。

• 奇数长度链表场景
  假设链表有n个节点（n为奇数，比如n=5），当快指针走到最后一个节点时，一共走了(n-1)/2次——因为每次走2步，(n-1)/2 *2 =n-1，刚好抵达第n个节点。此时慢指针同样走了(n-1)/2次，每次走1步，最终停在第(n-1)/2 +1 = (n+1)/2个节点，这正是链表的正中间节点。
  举个具体例子：节点1→2→3→4→5

  • 第1次移动：快指针到3，慢指针到2
  • 第2次移动：快指针到5（末尾），慢指针到3（中间节点）

• 偶数长度链表场景
  假设链表有n个节点（n为偶数，比如n=4），根据快指针的终止条件不同，会得到两种中间节点：

  1. 当快指针的next为null时停止：快指针走了n/2 -1次，抵达第n-1个节点，慢指针走了n/2 -1次，停在第n/2个节点（左中间）
  2. 当快指针本身为null时停止：快指针走了n/2次，抵达null，慢指针走了n/2次，停在第n/2 +1个节点（右中间）
     举例子：节点1→2→3→4
  • 情况1：快指针到3时，next是4的next即null，停止，慢指针到2（左中间）
  • 情况2：快指针走到null时，慢指针到3（右中间）

本质上，快指针移动的路程始终是慢指针的2倍，当快指针走完整个链表（或走到末尾前一个节点），慢指针刚好走完一半路程，自然落在链表的中间位置。

内容的提问来源于stack exchange，提问作者Tushar Kumar Roy