思路
很重要的一点:
# 每次迭代,tail 是在 head 之前
prev = tail
head = tail.next
# 每次tail会从head的前一个节点开始数数
for i in range(k):
tail = tail.next
if not tail:
# 说明最后一段节点数量小于k,不需要翻转
return hair.next
完整代码
class Solution:
def reverseSubList(self, head, tail):
prev = None
curr = head
while prev != tail:
tmp = curr.next
curr.next = prev
#更新
prev = curr
curr = tmp
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
# corner case
if head is None or head.next is None or k == 1:
return head
# 创建一个链表头
hair = ListNode(0)
hair.next = head
# 因为最后要返回 hair.next ,所以要新建一个移动的指针prev
prev = hair
tail = prev
while head:
# 每次tail会从head的前一个节点开始数数
for i in range(k):
tail = tail.next
if not tail:
# 说明最后一段节点数量小于k,不需要翻转
return hair.next
# 记录下tail的下一个节点,子链表翻转后需要拼接回来
aftr = tail.next
# 辅助函数作用,输入链表头和链表尾,翻转链表
self.reverseSubList(head, tail)
head, tail = tail, head
# 拼接子链表
prev.next = head
tail.next = aftr
# 更新
prev = tail
head = tail.next
return hair.next