萱仔求职复习系列——力扣

25. K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

我认为其实还是某一种反转链表，只不过变成一部分反转了，可以用递归来解决这个问题：

递归结束条件：当剩下的节点少于 k 个时，保持原有顺序，不再翻转。

递归处理：每次递归处理 k 个节点，翻转它们，然后将翻转后的部分与递归处理的剩余部分连接起来。

翻转部分链表：我们需要在每次递归时翻转 k 个节点，翻转完成后将新的头节点返回，并递归连接。

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # 检查链表是否有足够的节点进行翻转
        count = 0
        ptr = head
        while count < k and ptr:
            ptr = ptr.next
            count += 1
        
        # 如果节点数大于等于k，则进行翻转
        if count == k:
            # 翻转前k个节点
            prev = None
            curr = head
            for _ in range(k):
                next_node = curr.next
                curr.next = prev
                prev = curr
                curr = next_node
            
            # 递归处理剩余的部分，并连接回翻转后的部分
            head.next = self.reverseKGroup(ptr, k)
            
            # 返回新的头节点
            return prev
        
        # 如果节点数不足k，保持原样
        return head