Sponsored
Sponsored
This approach involves using a dummy node to handle the removal of nodes, including edge cases where the head node itself needs to be removed. We use a pointer to traverse the list, comparing each node's value with the target val. If the node needs to be removed, we adjust the pointers to skip the node. If not, we just move to the next node.
Time Complexity: O(n), where n is the number of nodes in the linked list, as we must traverse all nodes.
Space Complexity: O(1) because we are using constant extra space.
1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6class Solution:
7 def removeElements(self, head: ListNode, val: int) -> ListNode:
8 dummy = ListNode(0)
9 dummy.next = head
10 current = dummy
11 while current and current.next:
12 if current.next.val == val:
13 current.next = current.next.next
14 else:
15 current = current.next
16 return dummy.nextThe dummy node acts as a safe starting pointer. The current pointer traverses the list, and if the next node's value equals val, it is removed by skipping it. Otherwise, the loop continues with the next node. At the end, the head of the modified list is returned, which starts after the dummy node.
This approach employs a recursive strategy to tackle the problem. The idea is to attempt removing elements starting from the rest of the list and linking the current node to the result of this removal. If the head node itself needs removal, simply return the result of removing nodes from the rest of the list by moving the reference forward.
Time Complexity: O(n), as each node is processed exactly once.
Space Complexity: O(n), due to the recursion stack for n nodes in the longest path.
1 public int val;
public ListNode next;
public ListNode(int val = 0, ListNode next = null) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode RemoveElements(ListNode head, int val) {
if (head == null) return null;
head.next = RemoveElements(head.next, val);
return head.val == val ? head.next : head;
}
}The C# method processes the list recursively. If the node should be removed, it returns the processed form of the rest; if not, the current node remains and links to the subsequent nodes that have been evaluated and possibly pruned.