【迭代】25 -- k个一组翻转链表

思路

很重要的一点：

# 每次迭代，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