How to Answer: Remove all duplicates from a sorted list.
Advice and answer examples written specifically for a JavaScript Intermediate Level Linked Lists job interview.
3. Remove all duplicates from a sorted list.
This question focuses on JavaScript iteration.
You are given a sorted linked list of positive numbers. The list contains some duplicate nodes. Your task is to remove all the duplicate nodes such that the final list contains only those numbers which occurred once in the original node. You need to do this in place and return the new head (if changed).
/*Example*/
Given list:- 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
Expected list:- 1 -> 2 -> 5
Given list:- 1 -> 1 -> 1 -> 1 -> 2 -> 2 -> 3
Expected list:- 3Solution:
We will iterate over each node in the list. We will have two pointers: prev and curr. prev will point to the previous unique node.
2 -> 3 -> 3 -> 3 -> 4
| |
prev curr
In each iteration, we will compare the value of curr to the next of curr. If they are the same (means duplicates), we need to remove all the nodes with the same value altogether. We will iterate over each such duplicate node and reach the last node of the duplicate nodes. So, after such iterations, the pointers are:-
2 -> 3 -> 3 -> 3 -> 4
| |
prev curr (curr is pointing to the last node of the duplicate nodes)
We will remove these duplicate nodes by changing the next pointer of prev (by doing prev.next = curr.next).
If the values of curr and next of curr are not equal, we just check the other nodes by moving prev and curr one step forward. In the code, we check if the values are equal or not by using the arrow function isNextNodeSame.
We use a dummy node (also called sentinel node) for this purpose. A dummy node is a placeholder node that is used to initialize a new linked list when we don't have the head node. It may be the case where the duplicates are starting from the head node. Such cases are difficult to handle without using a dummy node. We create a dummy node with the value 0 (since the minimum value in the given list is 1) with its next pointing to the head of the given list. This makes the list starting from a unique node and does not need special case handling.
1 -> 1 -> 3 -> 3 -> 4 (without dummy node)
0 -> 1 -> 1 -> 3 -> 3 -> 4 (with dummy node)
class ListNode {
constructor(val, next) {
this.val = val || 0
this.next = next || null
}
}
/**
* @param {ListNode} head
* @return {ListNode}
*/
function removeDuplicates(head) {
const dummy = new ListNode(0, head)
let curr = head
let prev = dummy
const isNextNodeSame = (curr) => {
return curr.next && curr.val === curr.next.val
}
while (curr !== null) {
if (isNextNodeSame(curr)) {
while (isNextNodeSame(curr)) {
curr = curr.next
}
// we have reached the last of duplicate nodes
// remove all these duplicate nodes
prev.next = curr.next
} else {
prev = prev.next
}
curr = curr.next
}
return dummy.next
}n = number of nodes in the original list
Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021