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.