目录
链表应用 II
应用2：Leetcode.25
题目
输入：\(head = [1,2,3,4,5]\), \(k = 2\)
输出：\([2,1,4,3,5]\)
分析
这里，我们以前面题目中的用例，来说明算法的步骤。
为了避免讨论边界条件，这里，我们使用一个 \(dummy\) 节点指向 \(head\)。
首先，使用三个指针用于遍历主链表时记录子链表在主链表中的位置：
-
\(P_0\) ：记录子链表的首节点的前一个节点；
-
\(P_1\) 记录子链表的首节点；
-
\(tail\) 记录子链表的尾节点。
然后，我们遍历主链表，当tail向后移动k步之后，tail所指的元素就是子链表的尾节点，如下图所示：
此时，\(P_1\) 记录子链表的首节点 \(1\)，\(tail\) 指向待倒序的子链表的尾节点 \(2\)，同时，用 \(post\) 指针记录子链表的下一个节点：
然后，我们对子链表进行倒序，我们定义一个两个指针：
-
\(P_3\) 记录子链表的当前节点的前一个节点；
-
\(P_4\) 记录子链表的当前节点；
对子链表进行倒序操作：
子链表倒序的终止条件是 \(P_3\) 移动到子链表的 \(tail\) 节点；
倒序完成后，重新将 \(P_1\) 指向倒序后的子链表的首节点 \(2\)，\(tail\) 指向倒序后的子链表的尾节点 \(1\)，如下图所示：
将前驱指针 \(P_0\) 所指向的节点的 \(next\) 指针重新指向新的子链表首节点：
将子链表的尾结点的 \(next\) 指针重新指向主链表后驱节点 \(post\)：
重新指针 \(P_0\) 指向下一个子链表的前驱节点（即当前子链表的尾结点），将 \(P_1\) 指向下一个子链表的首节点：
因此，我们可以总结出算法步骤如下：
-
使用一个指针 \(tail\)，先让它指向 \(dummy\) 节点，并用它来遍历主链表，使用如下四个指针，记录子链表在主链表中的位置：
-
\(P_0\)：前驱指针，用于记录子链表首节点的前一个节点；
-
\(P_1\)：记录子链表的首节点；
-
\(tail\)：记录子链表的尾节点；
-
\(post\)：后驱指针，用于记录子链表尾节点的后一个节点；
-
-
指针 \(tail\) 每移动 \(k\) 步：
-
对 \(P_1\) 至 \(tail\) 所在的子链表进行倒序操作；
-
然后，重新将 \(tail\) 指向倒序后的子链表尾节点，将 \(head\) 指向倒序后的子链表首节点；
-
将倒序后的子链表重新接入主链表，即：
-
将前驱节点 \(P_0\) 的 \(next\) 指针指向的节点指向倒序后的子链表头节点 \(P1\)；
-
将倒序后的子链表尾节点 \(tail\) 的 \(next\) 指针指向的节点指向后驱节点 \(post\)；
-
-
重新将 \(P_0\) 指向当前子链表的尾节点 \(tail\)，即下一个子链表的前驱节点；
-
重新将 \(P_1\) 指向当前子链表的尾节点 \(tail\) 的下一个节点，即下一个子链表的头节点；
-
-
若指针 \(tail\) 移动的步数小于 \(k\) 步，则直接返回；
代码实现
from typing import Optional
class ListNode:
def __init__(self, val=0, _next=None):
self.val = val
self.next = _next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy = ListNode(0)
dummy.next = head
# p0指向子链表的前一个节点
p0 = dummy
# p1指向子链表的首节点
p1 = head
while p1:
tail = p0
# 查看剩余部分长度是否大于等于 k
for i in range(k):
tail = tail.next
if not tail:
return dummy.next
post = tail.next
# 对子链表倒序，并使p1指向将新的头节点，tail指向新的尾结点
p1, tail = self.reverse(p1, tail)
# 把子链表重新接回原链表
p0.next = p1
tail.next = post
# p0指向当前子链表的尾结点（即下一个子链表的前一个节点）
p0 = tail
# p1指向下一个子链表的首节点
p1 = tail.next
return dummy.next
def reverse(self, head: Optional[ListNode], tail: Optional[ListNode]):
p1 = None
p2 = head
while p1 != tail:
temp = p2.next
p2.next = p1
p1 = p2
p2 = temp
return tail, head