Linked List Delete Nodes¶
Table of Contents¶
- 203. Remove Linked List Elements (Easy)
- 3217. Delete Nodes From Linked List Present in Array (Medium)
- 83. Remove Duplicates from Sorted List (Easy)
- 82. Remove Duplicates from Sorted List II (Medium)
- 237. Delete Node in a Linked List (Medium)
- 1669. Merge In Between Linked Lists (Medium)
- 2487. Remove Nodes From Linked List (Medium)
- 1836. Remove Duplicates From an Unsorted Linked List (Medium) 👑
203. Remove Linked List Elements¶
"""
- Remove all elements from a linked list of integers that have value `val`.
"""
from typing import Optional
from leetpattern.utils import ListNode
# Iterative
def removeElements(head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummy = ListNode(0)
dummy.next = head
cur = dummy
while cur.next:
if cur.next.val == val:
cur.next = cur.next.next
else:
cur = cur.next
return dummy.next
# |-------------|-----------------|--------------|
# | Approach | Time | Space |
# |-------------|-----------------|--------------|
# | Iterative | O(N) | O(1) |
# |-------------|-----------------|--------------|
nums = [1, 2, 6, 3, 4, 5, 6]
val = 6
head = list_from_array(nums)
print(head)
# 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6
print(removeElements(head, val))
# 1 -> 2 -> 3 -> 4 -> 5
3217. Delete Nodes From Linked List Present in Array¶
from typing import List, Optional
from leetpattern.utils import ListNode, list_from_array, list_to_array
def modified_list(
nums: List[int], head: Optional[ListNode]
) -> Optional[ListNode]:
num_set = set(nums)
dummy = ListNode(0, head)
cur = dummy
while cur.next:
if cur.next.val in num_set:
cur.next = cur.next.next
else:
cur = cur.next
return dummy.next
def test_modified_list():
nums = [1, 2, 3]
head = list_from_array([1, 2, 3, 4, 5])
assert list_to_array(modified_list(nums, head)) == [4, 5]
83. Remove Duplicates from Sorted List¶
from typing import Optional
from leetpattern.utils import ListNode
# Linked List
def deleteDuplicates(head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return None
cur = head
while cur.next:
if cur.next.val == cur.val:
cur.next = cur.next.next
else:
cur = cur.next
return head
head = ListNode().create([1, 1, 2, 3, 3])
print(deleteDuplicates(head)) # 1 -> 2 -> 3
82. Remove Duplicates from Sorted List II¶
from typing import Optional
from leetpattern.utils import ListNode
# Linked List
def deleteDuplicates(head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0, head)
cur = dummy
while cur.next and cur.next.next:
val = cur.next.val
if cur.next.next.val == val:
while cur.next and cur.next.val == val:
cur.next = cur.next.next
else:
cur = cur.next
return dummy.next
head = ListNode().create([1, 1, 2, 3, 3, 4, 5])
print(deleteDuplicates(head)) # 2 -> 4 -> 5
237. Delete Node in a Linked List¶
"""
- Delete a node in a singly linked list. You are given only the node to be deleted.
"""
from leetpattern.utils import ListNode
def deleteNode(node: ListNode) -> None:
node.val = node.next.val
node.next = node.next.next
head = list_from_array([4, 5, 1, 9])
node = head.next
deleteNode(node)
print(head) # 4 -> 1 -> 9
1669. Merge In Between Linked Lists¶
2487. Remove Nodes From Linked List¶
"""
- Remove all nodes from a linked list that have a value greater than `maxValue`.
"""
from typing import Optional
from leetpattern.utils import ListNode, list_from_array, list_to_array
def remove_nodes_recursive(head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return None
head.next = remove_nodes_recursive(head.next)
if head.next and head.val < head.next.val:
return head.next
return head
def remove_nodes_iterative(head: Optional[ListNode]) -> Optional[ListNode]:
stack = []
cur = head
while cur:
while stack and cur.val > stack[-1].val:
stack.pop()
stack.append(cur)
cur = cur.next
dummy = ListNode()
cur = dummy
for node in stack:
cur.next = node
cur = cur.next
return dummy.next
def test_remove_nodes() -> None:
head = list_from_array([5, 2, 13, 3, 8])
assert (list_to_array(remove_nodes_recursive(head))) == [13, 8]
head = list_from_array([5, 2, 13, 3, 8])
assert (list_to_array(remove_nodes_iterative(head))) == [13, 8]