LeetCode题目25 hard:K个一组翻转链表 【分治策略 Python】

简介: LeetCode题目25 hard:K个一组翻转链表 【分治策略 Python】

问题描述

给你一个链表,每个链表上的节点数目为 n,请你将链表的每个 k 个节点反转,返回反转后的链表。

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

进一步说明:

  • 链表中节点的数目在范围 [1, 5000]
  • 0 <= Node.val <= 1000
  • 1 <= k <= 2000

示例

输入: head = [1,2,3,4,5], k = 2
 
输出: [2,1,4,3,5]

解释: 节点总数为 5,不是 2 的整数倍,因此最后剩下的一个节点保持原有顺序。

分治策略

分治策略,其中“分”是指将链表分成多个长度为 k 的部分,而“治”则是对每部分应用翻转操作。这样,可以高效地在单链表上实现复杂的数据重组,而不需要额外的空间开销(即空间复杂度为 O(1)),因为所有操作均在原链表上就地完成。

要求对链表中的节点进行局部翻转。主要思路是:

  1. 遍历链表,计算链表长度 n
  2. 对链表的每个 k 个节点进行翻转操作。如果链表剩余节点少于 k 个,则不进行翻转。
  3. 使用一个虚拟头节点简化边界处理,保持对翻转链表头部的引用。
  4. 使用三指针法(prev, curr, next)进行局部翻转。
  5. 注意处理每个翻转段的首尾连接问题。

代码实现

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def reverseKGroup(head, k):
    if not head or k == 1:
        return head
    
    # 创建一个虚拟头节点
    dummy = ListNode(0)
    dummy.next = head
    prev_group = dummy
    
    while True:
        kth = prev_group
        # 找到第 k 个节点
        for i in range(k):
            kth = kth.next
            if not kth:
                return dummy.next
        
        group_next = kth.next
        # 翻转 [prev_group.next, kth]
        prev, curr = kth.next, prev_group.next
        while curr != group_next:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        
        temp = prev_group.next
        prev_group.next = kth
        prev_group = temp
    
    return dummy.next
 
# 链表构造及调用
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i + 1]
head = nodes[0]
 
result = reverseKGroup(head, 2)
while result:
    print(result.val, end=" ")
    result = result.next

输出

2 1 4 3 5

图解说明

1.初始链表状态

链表:1 -> 2 -> 3 -> 4 -> 5,其中 k = 2。

2.添加虚拟头结点

为了方便操作,我们首先添加一个虚拟头结点(dummy node):

Dummy -> 1 -> 2 -> 3 -> 4 -> 5

3.第一次翻转过程(翻转1和2)

定位第k个节点

我们需要定位到第 k 个节点(2),这样我们就知道从哪里开始到哪里结束翻转。

Dummy -> 1 -> 2 -> 3 -> 4 -> 5
         |    |
         start kth

执行翻转

接下来,我们需要翻转从 start1)到 kth2)的部分。翻转操作如下:

Before:
Dummy -> 1 -> 2 -> 3 -> 4 -> 5
         |    |
         start kth
 
After:
Dummy -> 2 -> 1 -> 3 -> 4 -> 5

4.第二次翻转过程(翻转3和4)

定位第k个节点

和之前一样,我们移动到下一个未翻转的部分的第 k 个节点(4)。

Dummy -> 2 -> 1 -> 3 -> 4 -> 5
                    |    |
                   start kth

执行翻转

翻转从 start3)到 kth4)的部分。翻转操作如下:

Before:
Dummy -> 2 -> 1 -> 3 -> 4 -> 5
                    |    |
                   start kth
 
After:
Dummy -> 2 -> 1 -> 4 -> 3 -> 5

5.结果输出

最终的链表结构为:

Dummy -> 2 -> 1 -> 4 -> 3 -> 5

我们从虚拟头结点的下一个节点开始输出,即得到翻转后的链表:

2 -> 1 -> 4 -> 3 -> 5

算法分析

时间复杂度:O(n),其中 n 是链表的长度,我们需要遍历整个链表进行分组和翻转。 空间复杂度:O(1),只使用有限的几个指针,不需要额外空间。

核心思想

  • 虚拟头节点:引入虚拟头节点简化了链表头部的翻转逻辑,避免了复杂的边界条件判断。
  • 分组定位:通过双指针技术精确定位每k个节点的分组,确保了翻转的准确性和效率。
  • 局部翻转:在每个分组内部实现节点的就地翻转,使用了三指针策略来逐个调整节点指向。

解题思路:迭代 + 栈 方法

在这种方法中,我们将利用栈的特性来帮助我们实现链表的局部翻转。栈可以让我们简单地实现先进后出的顺序,正好符合翻转的需求。以下是使用迭代加栈方法进行 K 个一组翻转链表的详细步骤和完整代码实现。

算法步骤

1.    初始化:创建一个哑结点(dummy node)作为新链表的头部。这可以简化边界条件处理,使得头部处理逻辑与中间部分相同。

2.    遍历链表:使用指针 current 遍历原链表。

3.    填充栈:每遍历一个节点,就将其压入栈中。一旦栈的大小达到 k,就进行下一步。

4.    翻转操作:栈中元素数量达到 k 后,依次弹出栈中元素,并重建链表的这部分,从而实现局部翻转。

5.    连接链表:翻转后的链表部分需要与主链表正确连接。使用一个 prev 指针帮助记录每个部分的最后一个节点,以便连接。

6.    处理剩余部分:如果链表的长度不是 k 的整数倍,最后剩余的节点保持原有顺序连接。

python示例

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def reverseKGroup(head: ListNode, k: int) -> ListNode:
    if head is None or k == 1:
        return head
    # 创建一个哑结点作为新链表的头部
    dummy = ListNode(0)
    dummy.next = head
    current = head
    prev = dummy
    stack = []
    # 遍历链表
    while current:
        # 填充栈,直到栈的大小达到 k
        stack.append(current)
        next_temp = current.next
        
        if len(stack) == k:
            # 当栈的大小为 k 时,进行翻转
            while stack:
                if prev:
                    prev.next = stack.pop()
                prev = prev.next
        
            # 翻转完成后,连接剩余的部分
            prev.next = next_temp
        
        # 移动当前指针到下一个节点
        current = next_temp
    return dummy.next
# 链表节点创建和测试代码
# 创建链表 1->2->3->4->5
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
# 设置 k = 3
k = 3
new_head = reverseKGroup(node1, k)
# 打印新链表的结构
current = new_head
while current:
    print(current.val, end=" -> ")
    current = current.next

输出结果示例

对于链表 1->2->3->4->5 和 k = 3 的设置,输出应该是:

3 -> 2 -> 1 -> 4 -> 5 ->

这里的代码演示了如何使用栈结合迭代方法进行链表的局部翻转,并确保了整体链表结构的正确性。这种方法的空间复杂度为 O(k),时间复杂度为 O(n),是一种有效且易于理解的解决方案。


欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
4天前
|
算法 开发者 Python
惊呆了!Python算法设计与分析,分治法、贪心、动态规划...这些你都会了吗?不会?那还不快来学!
【7月更文挑战第10天】探索编程巅峰,算法至关重要。Python以其易读性成为学习算法的首选。分治法,如归并排序,将大问题拆解;贪心算法,如找零问题,每步求局部最优;动态规划,如斐波那契数列,利用子问题解。通过示例代码,理解并掌握这些算法,提升编程技能,面对挑战更加从容。动手实践,体验算法的神奇力量吧!
24 8
|
6天前
|
算法 Python
算法不再难!Python分治法、贪心、动态规划实战解析,轻松应对各种算法挑战!
【7月更文挑战第8天】掌握Python算法三剑客:分治、贪心、动态规划。分治如归并排序,将大问题拆解递归解决;贪心策略在每步选最优解,如高效找零;动态规划利用子问题解,避免重复计算,解决最长公共子序列问题。实例展示,助你轻松驾驭算法!**
17 3
|
4天前
|
算法 Python
Python算法高手进阶指南:分治法、贪心算法、动态规划,掌握它们,算法难题迎刃而解!
【7月更文挑战第10天】探索Python算法的精华:分治法(如归并排序)、贪心策略(如找零钱问题)和动态规划(解复杂问题)。通过示例代码揭示它们如何优化问题解决,提升编程技能。掌握这些策略,攀登技术巅峰。
|
5天前
|
算法 程序员 Python
算法小白到大神的蜕变之路:Python分治法、贪心、动态规划,一步步带你走向算法巅峰!
【7月更文挑战第9天】探索算法之旅,以Python解锁编程高手之路。分治法如二分查找,将复杂问题拆解;贪心算法解决活动选择,每次选取局部最优;动态规划求斐波那契数列,避免重复计算,实现全局最优。每一步学习,都是编程能力的升华,助你应对复杂挑战,迈向算法大师!
12 1
|
5天前
|
存储 算法 Python
Python算法界的秘密武器:分治法巧解难题,贪心算法快速决策,动态规划优化未来!
【7月更文挑战第9天】Python中的分治、贪心和动态规划是三大关键算法。分治法将大问题分解为小问题求解,如归并排序;贪心算法每步选局部最优解,不保证全局最优,如找零钱;动态规划存储子问题解求全局最优,如斐波那契数列。选择合适算法能提升编程效率。
15 1
|
5天前
|
存储 算法 Python
震撼!Python算法设计与分析,分治法、贪心、动态规划...这些经典算法如何改变你的编程世界!
【7月更文挑战第9天】在Python的算法天地,分治、贪心、动态规划三巨头揭示了解题的智慧。分治如归并排序,将大问题拆解为小部分解决;贪心算法以局部最优求全局,如Prim的最小生成树;动态规划通过存储子问题解避免重复计算,如斐波那契数列。掌握这些,将重塑你的编程思维,点亮技术之路。
14 1
|
5天前
|
存储 算法 大数据
Python算法高手的必修课:深入理解分治法、贪心算法、动态规划,让你的代码更智能!
【7月更文挑战第9天】在Python算法学习中,分治法(如归并排序)将大问题分解为小部分递归解决;贪心算法(如货币找零)在每步选择局部最优解尝试达到全局最优;动态规划(如斐波那契数列)通过存储子问题解避免重复计算,解决重叠子问题。掌握这三种方法能提升代码效率,解决复杂问题。
|
6天前
|
算法 索引 Python
逆袭算法界!Python分治法、贪心算法、动态规划深度剖析,带你走出算法迷宫!
【7月更文挑战第8天】分治法,如快速排序,将大问题分解并合并解;贪心算法,选择局部最优解,如活动选择;动态规划,利用最优子结构避免重复计算,如斐波那契数列。Python示例展示这些算法如何解决实际问题,助你精通算法,勇闯迷宫。
15 1
|
6天前
|
算法 索引 Python
Python算法设计与分析大揭秘:分治法、贪心算法、动态规划...掌握它们,让你的编程之路更加顺畅!
【7月更文挑战第8天】探索Python中的三大算法:分治(如快速排序)、贪心(活动选择)和动态规划(0-1背包问题)。分治法将问题分解求解再合并;贪心策略逐步求局部最优;动态规划通过记忆子问题解避免重复计算。掌握这些算法,提升编程效率与解决问题能力。
15 1
|
19天前
|
C语言
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
9 1