题解 | #链表中的节点每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: ListNode, k: int) -> ListNode:
        # 当 k = 1 时，也就不需要翻转任何元素了，此时直接将原链表输出即可
		if k == 1:
            return head
        
		# 设置两个列表，分别存放每一段的头节点和尾节点，通过计数器判断是在段头、段中还是段尾
        first = []
        tail = []
        count = 0
        node = head
        while head != None:
            if count % k == 0:
                first.append(head)
            elif count % k == k-1:
                tail.append(head)
            head = head.next
            count += 1
        # 以段尾是否为空作为判断条件，如果段尾为空，则有一下两种情况：
		# 1. 链表本身是空的
		# 2. k 的大小超过了链表的长度
		# 这两种情况都不需要改变链表，直接返回原链表即可，node保存了初始的头节点
		if tail == []:
            return node
        
		# 将所有段分为两部分处理，第一部分是第 0 段到第 n-2 段，第二部分是第 n-1 段
		# n 是尾节点的个数，当链表的长度是 k 的倍数时，恰好有 n 段（0 到 n-1）
		# 如果不是，则有 n+1 段，不过最后一段的长度小于 k，不需要进行任何处理
		# 对于前 （0，n-2） 段，直接反转链表，把原头节点指向下一段的尾节点即可
        n = len(tail)
        for i in range(n-1):
            pre, cur, nex = tail[i+1], first[i], first[i]
            for j in range(k):
                nex = nex.next
                cur.next = pre
                pre = cur
                cur = nex
        # 对于第 n-1 段，原头节点指向尾节点的下一个元素，并翻转链表
        pre, cur, nex = tail[n-1].next, first[n-1], first[n-1]
        for j in range(k):
            nex = nex.next
            cur.next = pre
            pre = cur
            cur = nex

        return tail[0]