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