python | #链表中的节点每k个一组翻转#

# 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 , k ):
        # write code here
        if head is None:
            return head
        if head.next is None:
            return head
        l = self.length(head) #链表的长度
        if k >l :
            return head 
        nums = l // k 
        cur = head #复制一个链表头
        new_head = ListNode(-1) #第一个切片的头，也就是新链表的头
        start = ListNode(-1) #每个切片的头
        end = ListNode(-1) #每个切片的尾

        start = head
        for j in range(k-1):
            cur = cur.next
        end = cur
        cur = cur.next
        end.next = None #截断链表
        start,end = self.reverse(start) #反转切片中链表
        new_head = start

        slice_end = end
        for i in range(nums -1 ):
            #截取一个长度为k的切片
            start = cur
            for j in range(k-1):
                cur = cur.next
            end = cur 

            # 进入该切片的下一个节点
            cur = cur.next

            end.next = None #截断链表

            start,end = self.reverse(start) #反转切片中链表

            slice_end.next = start

            slice_end = end
        slice_end.next = cur 
        return new_head
    def reverse(self,pHead):
        '''反转链表'''
        pre = ListNode(None) # 存储新链表的头
        cur = pHead 
        nex = ListNode(None) # 与cur一起遍历整个链表
        end = ListNode(None)
        while cur is not None:
            nex = cur.next
            if cur == pHead:#判断是否是头
                cur.next = None # 生成新链表的尾
                end = cur
            else:
                cur.next = pre # 反转节点的方向，指向新链表
            pre = cur #将新链表的头指向新节点
            cur = nex #将cur指向下个节点
            # 当遍历到最后一个节点时，nex会变成None，从而cur会变成None，退出循环
        return pre,end
    def length(self,head):
        l = 1 
        while head.next:
            head = head.next
            l+=1
        return l