25. K 个一组翻转链表(Hard)

题目描述

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

注意：如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

样例

Input：1->2->3->4->5, k = 2
Output: 2->1->4->3->5

Input：1->2->3->4->5, k = 3
Output: 3->2->1->4->5

题目解析

todo... 画图

Python代码示例

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        def reverse(head): # 链表翻转
            pre, cur = None, head 
            while cur:
                bak = cur.next 
                cur.next = pre 
                pre = cur 
                cur = bak 
            return pre 
        
        if not head or not head.next: # 单节点，空节点返回
            return head 
        
        p = head 
        for _ in range(k - 1):
            p = p.next 
            if not p:
                return head # 不满足就直接返回
        after = p.next 

        p.next = None # 断开链表
        cur = reverse(head) 
        head.next = self.reverseKGroup(after, k)
        return cur