K个一组翻转链表

思路， 首先一个哨兵结点可以帮我们省去判断边界的代码，建立哨兵，并且令dummy.next = head

将pre指向开头

循环开始，只要head不为nil

令tail = pre

tail往下走k步，只要tail为nil，立即返回dummy.next

nxt记录下tail.next，head即将走向的下一个结点

反转head到tail中的节点，返回新的head和tail

def reverse(head, tail):

​ 反转代码，令pre指向tail.next，cur指向head

​ while prev != tail:

​ nxt = cur.next

​ cur.next = prev

​ prev = cur

​ cur = nxt

​ return tail, head

将pre的next指向新的head

pre.next = head

尾部已相连

更新pre指向tail

head指向nxt

最终head为nil时退出循环

返回dummy.next

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        pre = dummy

        while head:
            tail = pre
            # 查看剩余部分长度是否大于k
            for _ in range(k):
                tail = tail.next
                if not tail:
                    return dummy.next
            nxt = tail.next
            head, tail = self.reverse(head, tail)
            # 把子链表重新串联起来
            pre.next = head
            pre = tail
            head = nxt
        return dummy.next

    def reverse(self, head, tail):
        prev = tail.next
        cur = head
        while prev != tail:
            cur.next, cur, prev = prev, cur.next, cur
        return tail, head