Description

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:

1Input: head = [1,2,6,3,4,5,6], val = 6
2Output: [1,2,3,4,5]

Example 2:

1Input: head = [], val = 1
2Output: []

Example 3:

1Input: head = [7,7,7,7], val = 7
2Output: []

Constraints:

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

Solution

This is a straight forward problem which requires iterating through the list and modifying pointers to next node if the node value is val. Here, because even the first element may have the value val, we need the previous node in order to remove this node. So, we will have to create a dummy node which will be previous to the head node.

 1class Solution {
 2    public ListNode removeElements(ListNode head, int val) {
 3        if (head == null) {
 4            return null;
 5        }
 6        ListNode dummy = new ListNode(0, head);
 7        ListNode current = head, previous = dummy;
 8        while (current != null) {
 9            if (current.val == val) {
10                previous.next = current.next;
11            } else {
12                previous = current;
13            }
14            current = current.next;
15        }
16        return dummy.next;
17    }
18}
  • Time Complexity: O(n)
  • Space Complexity: O(1)