2487. Remove Nodes From Linked List
https://leetcode.com/problems/remove-nodes-from-linked-list/
Level: Medium
Explanation
This is a simple problem but took me 30 minutes to solve. The keypoint is understand clearly the problem.
The requirement is "Remove every node which has a node with a greater value anywhere to the right side of it.
Which can be translated to
- No node to the right is greater than the current node
- No node to the left is smaller than the current node
Which can be further translated to
- Turn the linked list into a decreasing linked list
Decreasing Linked List is the key characteristic of the linked list we want to return.
Time:
Recursion
Then with recursion we can easily solve this problem. We assume the returned linked list must be decreasing.
If current node is greater than the first node in the returned linked list, attach the returned linked list to the current node and return the current node. So it's still decreasing.
If current node is smaller than the returned linked list, return the returned linked list. (Skip the current node)
Base case is when the current node is None, return None.
# 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]:
if head is None:
return None
ret = self.removeNodes(head.next)
if ret is None:
return head
if ret.val > head.val:
return ret
head.next = ret
return head
Stack
If recursion is not allowed, another intuitive way is to use stack/array.
We want a decreasing linked list, everything to the right must be smaller, but we don't know what's on the right.
With a regular array we can use index to iterate from right to left. So let's simplify this problem to a regular array.
"Remove all nodes in an array that prevent it to be decreasing."
Example 1
a = [5,2,13,3,8]
b = []
max_so_far = 0
for i in range(len(a) - 1, -1, -1):
if a[i] >= max_so_far:
max_so_far = a[i]
b.append(a[i])
print(b) # [8, 13]
b.reverse()
print(b) # [13, 8]
The problem is, with a linked list, we can't iterate from right to left.
So we reverse the array first so we can iterate from left to right.
Example 2
a = [5,2,13,3,8]
b = []
a.reverse()
max_so_far = 0
for i in range(len(a)):
if a[i] >= max_so_far:
max_so_far = a[i]
b.insert(0, a[i])
print(b) # [13, 8]
In the case of linked list, we can use a stack to reverse.
# 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 = []
cur = head
while cur: # construct the stack
stack.append(cur)
cur = cur.next
cur = stack.pop()
mx = cur.val
ret = ListNode(mx)
while stack: # iterate from left to right
cur = stack.pop()
if cur.val < mx:
continue
else:
new_node = ListNode(cur.val)
new_node.next = ret # insert current node to the left of linked list
ret = new_node
mx = cur.val
return ret
Reverse Twice
In Explanation we understood the nature of this problem: make the linked list decreasing order.
If we think from the groud up, this problem can be divided into 2 subproblems:
- Make a linked list increasing
- Reverse a linked list
- This is simple, it's LeetCode 206. Reverse Linked List. Using 3 pointers to reverse a linked list in place is one option.
Note: Here when I say "making a linked list increasing or decreasing", I am not talk about sorting, but removing the nodes that are not in the right order.
If we reverse the linked list and make it increasing, then reverse it back. This make it decreasing.
You may ask, why not just make it decreasing directly? The reason is, in the context of linked list and this problem. It's easier to make it increasing.
With a linked list, it's easy to keep the head and manipulate the rest of the linked list, then return head.
In the increasing linked list problem (no node to the right should be smaller than nodes on the left), we can easily remove the nodes that are not in the right order. If the current node is smaller than previous node, remove the current node. Most importantly, the head will never be removed because there is no node to its left.
To make decreasing linked list, if current node is greater than the previous node, remove the current node. The problem is, the rightmost node should always be kept because there is no node to the right of it. And the head should be able to be removed as all nodes are to the right of it.
This is why we need to reverse the linked list.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverse_list(self, head):
prev = None
current = head
next_temp = None
while current:
next_temp = current.next
current.next = prev
prev = current
current = next_temp
return prev
def increasing_order(self, head: Optional[ListNode]) -> Optional[ListNode]:
maximum = 0
cur = head
prev = None
while cur:
maximum = max(maximum, cur.val)
if cur.val < maximum:
prev.next = cur.next
# deleted = cur # this line is optional
cur = cur.next
# deleted.next = None # this line is optional
else:
prev = cur
cur = cur.next
return head # head is the rightmost node and could never be removed
def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
rev = self.reverse_list(head)
increasing = self.increasing_order(rev)
decreasing = self.reverse_list(increasing)
return decreasing
Conclusion
This problem is simple but tricky. The key is to understand the nature of the problem.
Solving it with recursion is the most elegant way. But if recursion is not allowed, we can use stack or reverse twice.
Recursion can have depth limit and introduces overhead. If the linked list can be super long the other options could be better.