Remove Linked List Elements
Learn three efficient approaches to remove nodes with a specific value from a linked list in Python. Explore direct removal, dummy head node, and recursive solutions. Complete with time/space complexity analysis and detailed examples. Perfect for coding interviews and data structure mastery.
LeetCode Link: 203. Remove Linked List Elements
Problem Definition
Given the head
of a linked list and an integer val
, remove all the nodes of the linked list that has Node.val == val
, and return the new head.
Example 1:
Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]
Example 2:
Input: head = [], val = 1
Output: []
Example 3:
Input: head = [7,7,7,7], val = 7
Output: []
Constraints:
- The number of nodes in the list is in the range
[0, 104]
. 1 <= Node.val <= 50
0 <= val <= 50
Thought Process
Let's take the linked list 1 → 4 → 2 → 4 as an example and remove the element 4
.
In this scenario, the removal operation involves making the next
pointer of the current node point directly to the node after the next one.
However, due to the nature of a singly linked list, each node can only point to the next node. In the example above, the second and fourth nodes (both containing the value 4) were removed. But what if the node to be deleted is the head node?
This brings us to two approaches for handling such operations:
- Directly removing nodes from the original linked list.
- Using a dummy head node to assist with the removal operation.
Let's first explore the direct removal from the original linked list:
In this method, we perform the removal directly on the original linked list without any additional setup.
The operation for removing the head node differs from removing other nodes. This is because other nodes in the linked list are removed by adjusting the next
pointer of their preceding node, but the head node has no preceding node.
So, how do we remove the head node? The solution is quite simple: just shift the head node one step forward, making the second node the new head. In this way, the original head node is effectively removed from the linked list.
Removing the head node differs from removing other nodes, as you've noticed. When writing code, you'll find that you need a separate logic block specifically to handle the removal of the head node.
So, is there a way to unify the logic for removing nodes from a linked list?
Yes, you can introduce a dummy head node. With a dummy head node, all nodes in the original linked list—including the original head—can be removed using the same logic.
Let's see how to set up a dummy head and apply it to the same linked list, where we aim to remove the element 1
.
Steps to Remove Element 1
:
- Start with the dummy node and iterate through the list.
- When the target node (with value
1
) is found, adjust the previous node'snext
pointer to skip this node. - Delete the node from memory (if necessary, depending on the language or system).
- At the end, return the new head by returning
dummyNode->next
. This points to the actual start of the modified list.
Solution 1
Directly use the original linked list to perform the node removal operation.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
# Remove head nodes with the given value
while head is not None and head.val == val:
tmp = head
head = head.next
# Remove non-head nodes with the given value
cur = head
while cur is not None and cur.next is not None:
if cur.next.val == val:
tmp = cur.next
cur.next = cur.next.next
else:
cur = cur.next
return head
Time Complexity: O(n)
Space Complexity: O(1)
Solution 2
Set up a virtual head node when performing the remove node operation.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
# Create dummy head
dummy_head = ListNode(next = head)
# traverse the list to delete target
current = dummy_head
while current.next:
if current.next.val == val:
current.next = current.next.next
else:
current = current.next
return dummy_head.next
Time Complexity: O(n)
Space Complexity: O(1)
Solution 3
This problem can also be solved using a recursive approach:
- Base case: For an empty linked list, no elements need to be removed.
- Recursive case: First, check if the value of the head node is equal to val. If it is, remove the head node; the answer will be the result of recursively processing the subsequent nodes after the head. If the value of the head node is not equal to
val
, then the answer will be a concatenation of the head node and the new linked list obtained by recursively processing its subsequent nodes.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
# Base case: if the list is empty, return None
if head is None:
return None
# Recursive case
if head.val == val:
new_head = self.removeElements(head.next, val)
del head # Optional: explicitly delete the node
return new_head
else:
head.next = self.removeElements(head.next, val)
return head
Time Complexity: O(n)
Space Complexity: O(n)
Discussion