题解 | #链表中的节点每k个一组翻转时间O(1n)#

# 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:
        if head == None:
            return head
        
        # 递归思想：把问题分解为两个部分，当前所有节点分组反转=最近这一组反转 + 这一组后面所有节点的分组反转

        # 先找到当前这一组的界限
        cur = head
        i = 0
        while i < k - 1 and cur != None:
            cur = cur.next
            i += 1
        if cur == None:
            return head
        nxtHead=cur.next 
        cur.next = None

        # 当前组反转
        pre = None
        nCur = head
        while nCur != None:
            nNxt = nCur.next
            nCur.next = pre
            pre = nCur
            nCur = nNxt
        
        # 当前组反转结果+这一组后面所有节点的分组反转
        head.next = self.reverseKGroup(nxtHead,k)

        # 返回当前组反转后的头结点
        return pre