leetcode2487.从链表中移除节点

简介: leetcode2487.从链表中移除节点

题目

给你一个链表的头节点 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

Problem: 2487. 从链表中移除节点

思路

使用单调栈,保留从左到右单调递减的数组,赋值给节点

在单调栈构造时,我们维护一个非递增的数组

如果发现下一个节点大于栈顶元素,则一直弹出栈顶元素,直到栈为空,或者栈顶元素大于下一个节点

复杂度

时间复杂度:

O ( n ) O(n)O(n)

空间复杂度:

O ( n ) O(n)O(n)

Code

# 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]:
        stack = []
        index = head
        while index!=None:
            while stack!=[] and stack[-1]<index.val:
                stack.pop()
            stack.append(index.val)
            index = index.next
        index = head
        for i in range(len(stack)):
            index.val = stack[i]
            if i!=len(stack)-1:
                index = index.next
        if index!=None : index.next = None 
        return head


目录
相关文章
|
2天前
24. 两两交换链表中的节点
24. 两两交换链表中的节点
19 6
|
2天前
|
算法 索引
【数据结构与算法 | 基础篇】[链表专题]力扣141, 142
【数据结构与算法 | 基础篇】[链表专题]力扣141, 142
|
2天前
|
算法
【数据结构与算法 | 基础篇】[链表专题]力扣82
【数据结构与算法 | 基础篇】[链表专题]力扣82
|
2天前
|
算法
【数据结构与算法 | 基础篇】[链表专题]力扣21, 234
【数据结构与算法 | 基础篇】[链表专题]力扣21, 234
|
2天前
|
算法
【数据结构与算法 | 基础篇】[链表专题]力扣LCR077, 83
【数据结构与算法 | 基础篇】[链表专题]力扣LCR077, 83
|
2天前
|
存储 算法
【数据结构与算法 | 基础篇】[链表专题]力扣206, 203, 19
【数据结构与算法 | 基础篇】[链表专题]力扣206, 203, 19
|
2天前
|
存储 C语言
链表—初始化指针变和创建新的节点------区别应用分析
链表—初始化指针变和创建新的节点------区别应用分析
|
2天前
|
算法 C语言
Leetcode_203.移除链表元素—C语言
Leetcode_203.移除链表元素—C语言
|
3天前
|
C语言 C++ 索引
力扣 138. 随机链表的复制
力扣 138. 随机链表的复制
|
4天前
剑指 Offer 18. 删除链表的节点
剑指 Offer 18. 删除链表的节点
11 0

热门文章

最新文章