King Of Interviews

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:

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:

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.

Remove Linked List Elements