【算法】【单调栈、递归 + 反转链表、Python3】力扣2487. 从链表中移除节点

发布时间:2024年01月05日

力扣2487. 从链表中移除节点


【算法】【单调栈、Python3】力扣2487. 从链表中移除节点

题目描述

给你一个链表的头节点 head

移除每个右侧有一个更大数值的节点。

返回修改后链表的头节点 head

示例 1:

输入:head = [5,2,13,3,8]
输出:[13,8]

解释:需要移除的节点是 5 ,2 和 3 。

  • 节点 13 在节点 5 右侧。
  • 节点 13 在节点 2 右侧。
  • 节点 8 在节点 3 右侧。

示例 2:

输入:head = [1,1,1,1]
输出:[1,1,1,1]

解释:每个节点的值都是 1 ,所以没有需要移除的节点。

提示:

  • 给定列表中的节点数目在范围 [1, 105] 内
  • 1 <= Node.val <= 105

单调栈解法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        stk = []  # 使用单调栈
        ans = ptr = head  # 初始化指针和答案链表头
        
        while ptr:
        	# 栈顶结点(左侧节点)比当前节点小,那就可以丢弃栈顶节点
            while stk and stk[-1].val < ptr.val:
                stk.pop()
            # 栈为空,即没有左侧的节点,当前元素自然就是头节点
            if not stk:
                ans = ptr
            # 栈不为空,将栈顶元素接入当前迭代的节点
            else:
                stk[-1].next = ptr
            # 入栈,在下一轮循环再检查这个节点是否保留
            stk.append(ptr)
            ptr = ptr.next
        
        return ans

步骤解析

  1. 引入必要的库和数据结构定义。

  2. 逆向思维:要移除每个右侧有一个更大数值的节点,即保留上述节点的右侧的更大节点。

  3. 使用单调栈,栈底到栈顶单调递减。创建指针 ptr 从链表头开始不断循环迭代。

  4. 在迭代中,判断栈顶元素是否比当前元素小,若是,则出栈,表示栈顶元素不可留。更新答案链表头。

  5. 更新链表连接关系,若栈非空,则将当前元素与栈顶元素连接;若栈为空,更新答案链表头。

  6. 将当前元素入栈,继续迭代。

  7. 返回最终答案链表头。

通过单调栈的巧妙运用,该算法能够高效地移除链表中每个右侧有更大数值的节点。

递归 + 反转链表解法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        right_max = 0
        ptr = ans = None

        # 定义深度优先搜索函数
        def dfs(node):
            nonlocal right_max, ans, ptr
            if node is None:
                return

            dfs(node.next)
            if node.val >= right_max:
                if ans is None:
                    ans = node
                    ptr = ans
                else:
                    ptr.next = node
                    ptr = ptr.next
                right_max = node.val

        # 定义链表反转函数
        def reverse(node, last_node):
            if node is None:
                nonlocal ans
                ans = last_node
                return

            next_node = reverse(node.next, node)
            if next_node is not None:
                next_node.next = node
            node.next = last_node

            return node

        # 调用深度优先搜索函数
        dfs(head)
        # 给逆序答案链表的尾节点的next指针补上一个None
        # 否则可能会出现环
        ptr.next = None
        # 调用链表反转函数
        reverse(ans, None)

        return ans

步骤解析:

  1. 引入必要的库和数据结构定义。

  2. 定义深度优先搜索函数 dfs,通过递归遍历链表,将符合条件的节点保存到 ans 链表中。同时,使用 ptr 指针进行链表的构建。

  3. 在深度优先搜索中,维护一个 right_max 变量,记录当前已经保存的节点中的最大值,以便比较是否需要保存当前节点。

  4. 定义链表反转函数 reverse,通过递归实现链表的反转,并更新 ans 链表头。

  5. 调用深度优先搜索函数 dfs,得到逆序的 ans 链表。

  6. ptr.next 设置为 None,断开逆序链表的尾部。

  7. 调用链表反转函数 reverse,得到最终答案链表。

  8. 返回最终答案链表 ans

解法对比与总结

递归 + 反转链表解法

提交结果
  • 执行用时: 392 ms,击败 72.59% 的 Python3 用户
  • 消耗内存: 62.41 MB,击败 18.70% 的 Python3 用户
性能分析
  • 执行用时较快,但消耗内存相对较高。
实现思路
  1. 使用递归(深度优先搜索)遍历链表,保存符合条件的节点。
  2. 通过递归实现链表的反转,得到最终答案链表。

单调栈解法

提交结果
  • 执行用时: 420 ms,击败 57.32% 的 Python3 用户
  • 消耗内存: 48.60 MB,击败 74.46% 的 Python3 用户
性能分析
  • 执行用时相对较慢,但消耗内存更低。
文章来源:https://blog.csdn.net/weixin_73108148/article/details/135393314
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。