LeetCode_25_困难_K个一组翻转链表

文章目录

1. 题目
2. 思路及代码实现（Python）
- 2.1 模拟

1. 题目

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

$k$ 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 $k$ 的整数倍，那么请将最后剩余的节点保持原有顺序。不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

是否可以设计一个只用 $O (1)$ 额外内存空间的算法解决此问题？

示例 1：

在这里插入图片描述

输入： $h e a d = [1, 2, 3, 4, 5], k = 2$
输出： $[2, 1, 4, 3, 5]$

示例 2：

输入： $h e a d = [1, 2, 3, 4, 5], k = 3$
输出： $[3, 2, 1, 4, 5]$

提示：

链表中的节点数目为 $n$
$1 <= k <= n <= 5000$
$0 <= N o d e . v a l <= 1000$

2. 思路及代码实现（Python）

2.1 模拟

我们需要把链表节点按照 $k$ 个一组分组，所以可以使用一个指针 $h e a d$ 依次指向每组的头节点。这个指针每次向前移动 $k$ 步，直至链表结尾。对于每个分组，我们先判断它的长度是否大于等于 $k$ 。若是，我们就翻转这部分链表，否则不需要翻转。

在翻转子链表的时候，我们不仅需要子链表头节点 $h e a d$ ，还需要有 $h e a d$ 的上一个节点 $p re$ ，以便翻转完后把子链表再接回 $p re$ 。但是对于第一个子链表，它的头节点 $h e a d$ 前面是没有节点 $p re$ 的，这时候可以新建一个节点，把它接到链表的头部，让它作为 $p re$ 的初始值，这样 $h e a d$ 前面就有了一个节点，我们就可以避开链表头部的边界条件。反复移动指针 $h e a d$ 与 $p re$ ，对 $h e a d$ 所指向的子链表进行翻转，直到结尾，我们就得到了答案。

该算法的时间复杂度为 $O (n)$ ， $n$ 为链表长度；空间复杂度为 $O (1)$ 。

class Solution:
    # 翻转一个子链表，并且返回新的头与尾
    def reverse(self, head: ListNode, tail: ListNode):
        prev = tail.next
        p = head
        while prev != tail:
            nex = p.next
            p.next = prev
            prev = p
            p = nex
        return tail, head

    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        hair = ListNode(0)
        hair.next = head
        pre = hair

        while head:
            tail = pre
            # 查看剩余部分长度是否大于等于 k
            for i in range(k):
                tail = tail.next
                if not tail:
                    return hair.next
            nex = tail.next
            head, tail = self.reverse(head, tail)
            # 把子链表重新接回原链表
            pre.next = head
            tail.next = nex
            pre = tail
            head = tail.next
        
        return hair.next