交换链表中的节点

记住「first 先走 k-1 步定位正数第 k,再用同步双指针把 second 推到倒数第 k」,下面逐帧套它。

先看整条链表 1→2→3→4→5→6→7,k=3。目标:找到正数第 3 个和倒数第 3 个,交换它们的值。从左往右数第 3 个是节点 3,从右往左数第 3 个是节点 5。

first 指针从头节点 1 出发。要走 k-1=2 步才能到正数第 3 个(头节点本身算第 1 个,所以走 k-1 步,不是 k 步)。

看 first 的下一个节点 2,准备往后挪一格。

第 1 步落位:first 到节点 2。还差一步。

看 first 的下一个节点 3,准备往后挪一格。

第 2 步落位:first 到节点 3。走满 k-1=2 步,first 就停在正数第 3 个节点 3 上,锁定它。

first 已锁定正数第 3 个节点(值 3,蓝色)。接下来要靠它找出倒数第 3 个。

现在 fast 从 first(节点 3)出发、second 从 head(节点 1)出发,两者相隔 k-1=2 格。只要让它俩同步往后走,等 fast 走到链尾,second 与链尾的距离也正好是 k-1,就停在倒数第 3 个上。

fast.next 存在(指向节点 4),说明 fast 还没到尾,两个指针一起往后走一格。

走一步:fast 到节点 4,second 到节点 2。

fast.next 存在(指向节点 5),说明 fast 还没到尾,两个指针一起往后走一格。

走一步:fast 到节点 5,second 到节点 3。

fast.next 存在(指向节点 6),说明 fast 还没到尾,两个指针一起往后走一格。

走一步:fast 到节点 6,second 到节点 4。

fast.next 存在(指向节点 7),说明 fast 还没到尾,两个指针一起往后走一格。

走一步:fast 到节点 7,已是链尾(fast.next 为空),循环停下。此刻 second 停在节点 5。

fast 已在链尾、second 与链尾正好相隔 k-1=2 格,所以 second 就是倒数第 3 个节点(值 5)。两个目标都定位好了。

开始交换:正数第 3 个是 3、倒数第 3 个是 5。下面只换这两个节点的值,不动任何指针。

交换第一步:用一个临时变量存住 first 的值 3,免得马上被覆盖。

交换第二步:把 second 的值 5 写进 first 的位置,first 这个节点现在显示 5。

交换第三步:把暂存的 3 写进 second 的位置。两个值就互换好了。

交换完成:链表变成 1,2,5,4,3,6,7。回头看,我们只用一趟双指针定位了正数第 k 和倒数第 k,再换两个值就收工,全程 O(1) 额外空间、一根指针没改。

边界:k=1 换头尾;k 在正中两指针重合不变;单节点不变。

两个高频追问:换值比换节点省事;一趟双指针无需先求长度。