How hard is LeetCode 2487. Remove Nodes From Linked List?

LeetCode 2487. Remove Nodes From Linked List is rated Medium on LeetCode.

What is the time complexity of LeetCode 2487. Remove Nodes From Linked List?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 2487. Remove Nodes From Linked List?

The Python solution on this page uses O(n), where n is the length of the linked list auxiliary space.

What topics does LeetCode 2487. Remove Nodes From Linked List cover?

LeetCode 2487. Remove Nodes From Linked List is tagged Stack, Recursion, Linked List and Monotonic Stack on LeetCode.

Remove Nodes From Linked List — LeetCode 2487 Python Solution

MediumStackRecursionLinked ListMonotonic Stack

Problem: #2487
Pattern: Linked List
Reading time: 4 min
Source: leetcode.com

The problem

You are given the head of a linked list. Remove every node which has a node with a greater value anywhere to the right side of it.

Example

Input: head = [5,2,13,3,8]
Output: [13,8]
Explanation: The nodes that should be removed are 5, 2 and 3.

Python solution

Python

# 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]:
        nums = []
        while head:
            nums.append(head.val)
            head = head.next
        stk = []
        for v in nums:
            while stk and stk[-1] < v:
                stk.pop()
            stk.append(v)
        dummy = ListNode()
        head = dummy
        for v in stk:
            head.next = ListNode(v)
            head = head.next
        return dummy.next

Complexity

Measure	Complexity
Time	O(n)
Space	O(n), where n is the length of the linked list auxiliary

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 2487. Remove Nodes From Linked List is filed here because LeetCode tags it Linked List, which is the vocabulary this hub collects.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2487. Remove Nodes From Linked List?: LeetCode 2487. Remove Nodes From Linked List is rated Medium on LeetCode.
What is the time complexity of LeetCode 2487. Remove Nodes From Linked List?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 2487. Remove Nodes From Linked List?: The Python solution on this page uses O(n), where n is the length of the linked list auxiliary space.
What topics does LeetCode 2487. Remove Nodes From Linked List cover?: LeetCode 2487. Remove Nodes From Linked List is tagged Stack, Recursion, Linked List and Monotonic Stack on LeetCode.