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

from itertools import count
from pickle import encode_long
from ast import NodeTransformer
# 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:
        # write code here
		#判断是否为空链表或单节点链表
        if head is None or head.next is None :
            return head
		#如果k为1则不用反转
        if k == 1 :
            return head
		#获得链表长度
        len = 0
        node = head
        while(node is not None):
            len += 1
            node = node.next
		
		#创建虚拟头节点
        dummy = ListNode(-1)
        dummy.next = head
		#创建节点prev，帮助我们链接反转后的链表段
        prev = dummy
        count = int(len / k)
		#创建start和end节点，分别确定要反转的链表段的第一个节点和最后的一个节点的下一个节点
        start = head
        end = start
        for i in range(count):
            for j in range(k):
                end = end.next
			#p，q节点用于反转链表
            p = start
            q = start.next
            while(q != end):
                p.next = q.next
                q.next = start
                start = q
                q = p.next
			#第一次：将头节点指向反转后的链表的第一个节点，之后的循环：让上一段链表段的最后一个节点和下一个链表段的第一个节点相连
            prev.next = start
			#将prev节点指向反转后的链表的最后一个节点，方便之后和下一段反转后的链表相连
            prev = p
			#确定新的反转范围
            start = end
		#返回
        return dummy.next