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 LinkedList, 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) |
# |-------------|-----------------|--------------|
def test_removeElements():
# Test case 1: Remove elements from middle and end
nums = [1, 2, 6, 3, 4, 5, 6]
val = 6
ll = LinkedList(nums)
assert ll.to_array() == [1, 2, 6, 3, 4, 5, 6]
result = removeElements(ll.head, val)
ll_result = LinkedList(result)
assert ll_result.to_array() == [1, 2, 3, 4, 5]
# Test case 2: Remove all elements
ll2 = LinkedList([7, 7, 7, 7])
result2 = removeElements(ll2.head, 7)
assert result2 is None
# Test case 3: Remove elements from beginning
ll3 = LinkedList([1, 1, 2, 3, 4])
result3 = removeElements(ll3.head, 1)
ll_result3 = LinkedList(result3)
assert ll_result3.to_array() == [2, 3, 4]
# Test case 4: No elements to remove
ll4 = LinkedList([1, 2, 3, 4])
result4 = removeElements(ll4.head, 5)
ll_result4 = LinkedList(result4)
assert ll_result4.to_array() == [1, 2, 3, 4]
3217. Delete Nodes From Linked List Present in Array¶
from typing import List, Optional
from leetpattern.utils import LinkedList, ListNode
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():
ll = LinkedList([1, 2, 3, 4, 5])
ll = LinkedList(modified_list([2, 3], ll.head))
assert ll.to_array() == [1, 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 LinkedList, ListNode
def deleteNode(node: ListNode) -> None:
node.val = node.next.val
node.next = node.next.next
def test_deleteNode():
# Test case 1: Delete middle node
ll = LinkedList([4, 5, 1, 9])
assert ll.to_array() == [4, 5, 1, 9]
node = ll.head.next # node with value 5
deleteNode(node)
assert ll.to_array() == [4, 1, 9]
# Test case 2: Delete another middle node
ll2 = LinkedList([4, 5, 1, 9])
node2 = ll2.head.next.next # node with value 1
deleteNode(node2)
assert ll2.to_array() == [4, 5, 9]
1669. Merge In Between Linked Lists¶
2487. Remove Nodes From Linked List¶
from typing import Optional
from leetpattern.utils import LinkedList, ListNode
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:
ll = LinkedList([5, 2, 13, 3, 8])
ll = LinkedList(remove_nodes_recursive(ll.head))
assert ll.to_array() == [13, 8]
ll = LinkedList([5, 2, 13, 3, 8])
ll = LinkedList(remove_nodes_iterative(ll.head))
assert ll.to_array() == [13, 8]