Question

LeetCode Link | 203. Remove Linked List Elements | Easy

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.

Constrains

  • The number of nodes in the list is in the range [0, 10^4].
  • 1 <= Node.val <= 50
  • 0 <= val <= 50

Example

Example 1

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: []

Solution Approach

Method: Dummy Node

Constrains

  • None

This method does not have any limitations.

Although in daily practice with LeetCode problems, the linked list nodes are usually predefined and you can use them directly, it’s still important to learn how to define a linked list yourself to prepare for situations where you might need to write it from scratch in an interview.

1
2
3
4
5
6
7
8
class ListNode {
  val: number
  next: ListNode | null
  constructor(val?: number, next?: ListNode | null) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
  }
}

Concept Explanation

This problem is a basic knowledge of linked list, which don’t require any skills to solve it. To remove a node in linked list are just unlink it from previous node which make previous node link to the next node as the figure shown below:

Remove Node

The only tricky node is the head node, where we need to assign next node to be the head node which could cause a extra lines to handle this situation.

Remove Head Node

Yes, you can use a uniform logic to remove nodes from a linked list. Indeed, setting a dummy head node can standardize the removal of all nodes in the original linked list. Let’s see how to set up a dummy head. We will continue with the same linked list, removing the element 2.

Dummy Node

Here, we add a dummy head node as the new head of the list, and now we need to remove the old head node element 2. By doing this, we unify the method of removing other nodes in the list.

Code

  • Time complexity: O(n)
  • Space complexity: O(1)

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function removeElements(head: ListNode | null, val: number): ListNode | null {
    // Dummy Node used for remove head node if need
    const data = new ListNode(0, head);
    let pre = data, cur = data.next;
    while (cur) {
        if (cur.val === val) {
            pre.next = cur.next
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return data.next;
};

Conclusion

Nothing really need to learn, just remember how to write the structure of the Linked List and use the dummy node if you want to unify your implementation.