K个一组翻转链表

问题简述

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：
    你可以设计一个只使用常数额外空间的算法来解决此问题吗？
    你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

25. K 个一组翻转链表 - 力扣（LeetCode）

思路

• 关键是确定 4 个位置, 即待反转子链表的头节点 sub_head, 及其前一个节点 pre, 尾节点 sub_tail, 及其下一个节点 nxt;

• 细节:

  • 设置伪头节点, 遍历时先找到 pre, 在确定 h, t, nxt;

  • 不足 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 reverse(self, head):
        pre, cur = None, head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre, head

    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:

        dummy = cur = ListNode(next=head)  # 设置伪头节点
        while cur:
            pre = cur  # 子链表头节点的前一个节点
            for _ in range(k):
                if not cur.next:
                    return dummy.next
                cur = cur.next
            sub_head = cur.next  # 子链表尾节点的下一个节点
            cur.next = None  # 断开子链表
            pre.next, sub_tail = self.reverse(pre.next)  # 反转子链表, 返回反转后的头尾节点
            sub_tail.next = sub_head
            cur = sub_tail

        return dummy.next