Skip to main content

Remove Linked List Elements


Remove Linked List Elements: 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:

image

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

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

Try this Problem on your own or check similar problems:

  1. Remove Element
  2. Delete Node in a Linked List
  3. Delete the Middle Node of a Linked List
Solution:
public ListNode removeElements(ListNode head, int val) {
if (head == null) return null;

ListNode dummy = new ListNode(-1, head), curr = dummy;

while(curr.next != null){
if(curr.next.val == val){
curr.next = curr.next.next;
}
else{
curr = curr.next;
}
}

return dummy.next;
}

Time/Space Complexity:
  • Time Complexity: O(n)
  • Space Complexity: O(1)

Explanation:

The dummy node is called sentinel, and you will see it many linked list problems, it's an artificial node holding no real value ("real" in context of linked list values) and pointing to the head of the list (or the end). Why do we need it? Well, it comes in handy when we must remove the head of the linked list (head node has value equal to val). So, we define the dummy node with also curr which will serve as our list iterator. We iterate through the list and we're checking if curr.next != null instead of curr != null. You could do it with curr != null, but then you would need a prev pointer, so you can relink if the curr node has value of val. So everytime we face next element with value val we "skip it" by relinking to the next node after it, otherwise we just move the iterator to the next node that contains different value than val. Dummy node will be pointing to the new head so we just have to return dummy.next. We're iterating over the list with n nodes so we have linear time complexity.