当前位置：首页 > article >正文

LeetCode【0025】K个一组翻转链表

article 2024/11/14 20:43:01

本文目录

1 中文题目
2 求解方法：头插法
- 2.1 方法思路
- 2.2 Python代码
- 2.3 复杂度分析
3 题目总结

1 中文题目

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

注意：

不能只是单纯的改变节点内部的值，而是需要实际进行节点交换
需要设计一个只用 $O (1)$ 额外内存空间的算法解决此问题

示例：
在这里插入图片描述

提示：

链表中的节点数目为 $n$
$\leq k \leq n \leq 5000$
$\leq Node.val \leq 1000$

2 求解方法：头插法

2.1 方法思路

方法核心

使用虚拟头节点简化边界情况处理。先计算链表长度，确保每组都有k个节点，并采用头插法进行区间内的节点翻转

实现步骤

初始化：
a. 创建虚拟头节点
b. 计算链表总长度
翻转过程：
a. 确定待翻转区间
b. 使用头插法逐个翻转节点
c. 更新指针位置和剩余长度
结束条件：
剩余节点数小于k时停止翻转

方法示例

输入：1->2->3->4->5, k=2

1. 初始状态：
dummy->1->2->3->4->5
length = 5

2. 第一次翻转(1,2)：
a. pre = dummy, curr = 1, next = 2
b. 翻转后：dummy->2->1->3->4->5
c. pre = 1, length = 3

3. 第二次翻转(3,4)：
a. pre = 1, curr = 3, next = 4
b. 翻转后：dummy->2->1->4->3->5
c. pre = 3, length = 1

4. 剩余节点数小于k，结束翻转
最终结果：2->1->4->3->5

2.2 Python代码

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # 如果链表为空或k=1，无需翻转
        if not head or k == 1:
            return head
        
        # 创建虚拟头节点
        dummy = ListNode(0)
        dummy.next = head
        # pre指向待翻转区间的前一个节点
        pre = dummy
        
        # 计算链表长度
        length = 0
        curr = head
        while curr:
            length += 1
            curr = curr.next
        
        # 当剩余节点数大于等于k时，继续翻转
        while length >= k:
            # curr指向待翻转区间的第一个节点
            curr = pre.next
            # next指向待翻转区间的下一个节点
            next = curr.next
            
            # k-1次翻转操作
            for i in range(k-1):
                # 将next插入到pre后面
                curr.next = next.next
                next.next = pre.next
                pre.next = next
                next = curr.next
            
            # 更新指针和剩余长度
            pre = curr
            length -= k
        
        return dummy.next