题解 | #牛群的重新分组#

• 题目考察的知识点 : 链表的反转
• 题目解答方法的文字分析：

1. 定义一个dummy节点指向头部便于操作
2. 通过尾指针tail检查剩余长度是否>=k
3. 反转以head开头长度为k的子链表
4. 将反转后的子链表接回原链表
5. 将pre指针后移,继续处理下一个子链表

• 本题解析所用的编程语言： Python
• 完整且正确的编程代码

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @param k int整型 
# @return ListNode类
#
class Solution:
    def reverseKGroup(self , head: ListNode, k: int) -> ListNode:
        def reverse(head, tail):
            pre = tail.next
            cur = head
            while pre != tail:
                nex = cur.next
                cur.next = pre
                pre = cur
                cur = nex
            return tail, head
            
        dummy = ListNode(0)
        dummy.next = head
        pre = dummy

        while head:
            tail = pre
            # 检查剩余部分长度是否大于等于 k 
            for i in range(k):
                tail = tail.next
                if not tail:
                    return dummy.next

            nex = tail.next
            head, tail = reverse(head, tail)
            # 把子链表重新接回原链表
            pre.next = head 
            tail.next = nex
            pre = tail
            head = tail.next
    
        return dummy.next