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

链表中的节点每k个一组翻转_牛客题霸_牛客网

问题简述

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。

思路（不使用栈）

• 每次取 k 个节点，反转后接入原链表；

• 细节很多，不容易写对，详见代码；

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:

        dummy = ListNode(0)
        dummy.next = head
        
        def reverse(h):
            """标准的反转链表"""
            pre, cur = None, h
            while cur:
                nxt = cur.next
                cur.next = pre
                pre = cur
                cur = nxt
            return pre, h  # 反转后的首尾节点
        
        # [l, r] 分别指向子链表的首尾节点，
        # 小技巧，把 r 初始化为 l 的前一个节点，那么移动 k 次后，就刚好是第 k 个节点
        pre = dummy 
        l, r = head, pre
        while l:
            for _ in range(k):
                r = r.next
                if not r:  # 不足 k 个节点，提前返回
                    return dummy.next
            
            # 断开 r 和 r.next 就是一个标准的链表反转；否则需要调整尾结点的判断，不推荐
            nxt, r.next = r.next, None
            l, r = reverse(l)  # 得到反转后的首尾节点
            pre.next, r.next = l, nxt  # 接入原链表
            pre, l = r, nxt   # 更新下一组 pre, l, r；
            # 因为反转后 r 刚好就是下一组 l 的前一个节点，所以不用再更新
        
        return dummy.next