Leetcode 203. Remove Linked List Elements
Problem Explanation
This problem asks for a function that goes through a list of integers and removes all elements that match a given integer. The list is provided in the form of a linked list, which is a standard data structure consisting of a series of nodes or elements that are "linked" or connected to each other. Each node in a linked list usually contains some data value and a reference or pointer to the next node in the list.
Given the list 1->2->6->3->4->5->6
and the number 6
, the function should remove all occurrences of 6
and return the resulting list 1->2->3->4->5
.
Solution Approach
The proposed solution will loop through the list and compare each node's value to the target integer. If the two numbers don't match, the current node is added to the resultant list. If they do match, the current node is simply skipped. The "dummy" node is used as a place holder at the start of the resultant list. This ensures that all nodes can be added into the resultant list in the same way, even if the first node matches the target integer.
Let's illustrate this with an example. Given the list 1->2->6->3->4->5->6
and the target integer 6
, let's signal "->" as the link between nodes:
1 2 3Starting list: 1->2->6->3->4->5->6 4 ^ 5 (dummy) 6 7Checking node 1: 1 != 6. Add 1 to the resultant list: 1 8Dummy list becomes: 1 9Checking 2: 2 != 6. Add 2 to the resultant list: 1 -> 2 10Skipping 6: 6 == 6. Don't add to the resultant list. 11Checking 3: 3 != 6. Add 3 to the resultant list: 1 -> 2 -> 3 12... and so on until the end: final list 1 -> 2 -> 3 -> 4 -> 5
After completing the loop, the "dummy" node's next
reference points to the start of the resultant list, so dummy.next
can be returned as the solution.
Solutions
Python Solution
1 2python 3class Solution: 4 def removeElements(self, head, val): 5 dummy = ListNode(0) 6 dummy.next = head 7 cur = dummy 8 9 while cur and cur.next: 10 if cur.next.val == val: 11 cur.next = cur.next.next 12 else: 13 cur = cur.next 14 return dummy.next
Java Solution
1 2java 3class Solution { 4 public ListNode removeElements(ListNode head, int val) { 5 ListNode dummy = new ListNode(0); 6 dummy.next = head; 7 ListNode cur = dummy; 8 while(cur != null && cur.next != null){ 9 if(cur.next.val == val) 10 cur.next = cur.next.next; 11 else 12 cur = cur.next; 13 } 14 return dummy.next; 15 } 16}
JavaScript Solution
1 2javascript 3var removeElements = function(head, val) { 4 let dummy = new ListNode(0); 5 dummy.next = head; 6 let cur = dummy; 7 while(cur && cur.next) { 8 if(cur.next.val === val) 9 cur.next = cur.next.next; 10 else 11 cur = cur.next; 12 } 13 return dummy.next; 14};
C++ Solution
1 2cpp 3class Solution { 4public: 5 ListNode* removeElements(ListNode* head, int val) { 6 ListNode dummy(0); 7 dummy.next = head; 8 ListNode* cur = &dummy; 9 while(cur && cur->next) { 10 if(cur->next->val == val) 11 cur->next = cur->next->next; 12 else 13 cur = cur->next; 14 } 15 return dummy.next; 16 } 17};
C# Solution
1 2csharp 3public class Solution { 4 public ListNode RemoveElements(ListNode head, int val) { 5 ListNode dummy = new ListNode(0); 6 dummy.next = head; 7 ListNode cur = dummy; 8 while(cur != null && cur.next != null) { 9 if(cur.next.val == val) 10 cur.next = cur.next.next; 11 else 12 cur = cur.next; 13 } 14 return dummy.next; 15 } 16}
In all the solutions above, we first create a dummy node and a current node initially pointing to the dummy. We then start the while loop checking if the next
node's value is equal to the target value. If it is, we skip the node by pointing next
to next.next
. If not, we just move the current node forwards. Once the loop is finished, we return dummy.next
, which is the head of the linked list without the target elements.## Complexity Analysis
The time complexity of this approach is O(n), where n is the total number of nodes in the linked list. This is because we are traversing each node exactly once.
The space complexity is O(1), because we are not using any additional space that scales with the size of the input. We are only using a fixed amount of space to keep track of the "dummy" node and the current node.
Conclusion
This problem teaches us how to handle linked list data structures, specifically how to traverse a linked list, how to skip a node and how to return a new linked list from a given linked list. We used a "dummy" node as a workaround to handle edge cases where the first node matches the target integer. One can see that with this approach we simplified our code, and made it cleaner. As a result, a dummy node can be very useful when dealing with linked list problems.
The above described approach can be easily applied in Python, Java, JavaScript, C++ and C#. Although the syntax might slightly change from one programming language to another, the idea and logic behind the solution remain the same.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.