Remove Linked List Elements

Companies:
  • Bloomberg Interview Questions
  • Google Interview Questions

Companies: Pure Storage, Bloomberg, Google, Capital one

Remove all elements from a linked list of integers that have value val.

Example:

Input: 1->2->3->2->4->5 val = 2

Output: 1->3->4->5

Solution:

This problems looks simple as long as we have to delete the nodes from the middle. But when it comes to deletion of the head of the linkedlist, we need to find an appraoch to solve this problem.

To delete the head of the linked list, we must have predefined head to replace it while deleting. This is done through pseudo-head known as senital node. This will allow us to remove the head of the linked list if needed. This will not disturb our original linked list.

Implementation:

Java:

class Solution {
  public ListNode removeElements(ListNode head, int val) {
    ListNode sentinel = new ListNode(0);
    sentinel.next = head;

    ListNode prev = sentinel, curr = head;
    while (curr != null) { //if current node is not null
      if (curr.val == val) prev.next = curr.next; //compare the value with the given value
      else prev = curr; 
      curr = curr.next;
    }
    return sentinel.next;
  }
}

Complexity Analysis:

  • Time Complexity: O(n)

  • Space Complexity: O(1).

Scroll to Top