Learn the efficient way to remove duplicates from a linked list and keep your data structure clean.

easy

Published At

6/4/2021

You're given the head of a Singly Linked List whose nodes are in sorted order with respect to their values. Write a function that returns a modified version of the Linked List that doesn't contain any nodes with duplicate values. The Linked List should be modified in place (i.e., you shouldn't create a brand new list), and the modified Linked List should still have its nodes sorted with respect to their values.

Each LinkedList node has an integer value as well as a next node pointing to the next node in the list or to None / null if it's the tail of the list.

### Sample Input

js
``linkedList = 1 -> 1 -> 3 -> 4 -> 4 -> 4 -> 5 -> 6 -> 6 // the head node with value 1``
js
``linkedList = 1 -> 1 -> 3 -> 4 -> 4 -> 4 -> 5 -> 6 -> 6 // the head node with value 1``

### Sample Output

js
``1 -> 3 -> 4 -> 5 -> 6 // the head node with value 1``
js
``1 -> 3 -> 4 -> 5 -> 6 // the head node with value 1``

### Hints

Hint 1

The brute-force approach to this problem is to use a hash table or a set to keep track of all node values that exist while traversing the linked list and to simply remove nodes that have a value that already exists. This approach works, but can you solve this problem without using an auxiliary data structure?

Hint 2

What does the fact that the nodes are sorted tell you about the location of all duplicate nodes? How can you use this fact to solve this problem with constant space?

Hint 3

Since the linked list's nodes are sorted, you can loop through them and, at each iteration, simply remove all successive nodes that have the same value as the current node. For each node, change its next pointer to the next node in the linked list that has a different value. This will remove all duplicate-value nodes.

Optimal Space & Time Complexity

O(n) time | O(1) space - where n is the number of nodes in the Linked List

Solution-1
js
``````// This is an input class. Do not edit.
constructor(value) {
this.value = value;
this.next = null;
}
}

while(currentNode) {
let nextNode = currentNode.next
while (nextNode !== null && currentNode.value == nextNode.value) {
nextNode = nextNode.next
}

currentNode.next = nextNode
currentNode = nextNode
}

}

/*

{
"nodes": [
{"id": "1", "next": "1-2", "value": 1},
{"id": "1-2", "next": "1-3", "value": 1},
{"id": "1-3", "next": "2", "value": 1},
{"id": "2", "next": "3", "value": 3},
{"id": "3", "next": "3-2", "value": 4},
{"id": "3-2", "next": "3-3", "value": 4},
{"id": "3-3", "next": "4", "value": 4},
{"id": "4", "next": "5", "value": 5},
{"id": "5", "next": "5-2", "value": 6},
{"id": "5-2", "next": null, "value": 6}
]
}
}

1, 1, 1, 3, 4, 4, 4, 5, 6, 6

currentNode nextNode nexterNode
1 1 1

*/``````
Solution-1
js
``````// This is an input class. Do not edit.
constructor(value) {
this.value = value;
this.next = null;
}
}

while(currentNode) {
let nextNode = currentNode.next
while (nextNode !== null && currentNode.value == nextNode.value) {
nextNode = nextNode.next
}

currentNode.next = nextNode
currentNode = nextNode
}

}

/*

{
"nodes": [
{"id": "1", "next": "1-2", "value": 1},
{"id": "1-2", "next": "1-3", "value": 1},
{"id": "1-3", "next": "2", "value": 1},
{"id": "2", "next": "3", "value": 3},
{"id": "3", "next": "3-2", "value": 4},
{"id": "3-2", "next": "3-3", "value": 4},
{"id": "3-3", "next": "4", "value": 4},
{"id": "4", "next": "5", "value": 5},
{"id": "5", "next": "5-2", "value": 6},
{"id": "5-2", "next": null, "value": 6}
]
}
}

1, 1, 1, 3, 4, 4, 4, 5, 6, 6

currentNode nextNode nexterNode
1 1 1

*/``````

🦜

Do you have any questions, or simply wish to contact me privately? Don't hesitate to shoot me a DM on Twitter.

Have a wonderful day.
Abhishek 🙏

## Join My Exclusive Newsletter Community

Step into a world where creativity intersects with technology. By subscribing, you'll get a front-row seat to my latest musings, full-stack development resources, and exclusive previews of future posts. Each email is a crafted experience that includes:

• In-depth looks at my covert projects and musings to ignite your imagination.
• Handpicked frontend development resources and current explorations, aimed at expanding your developer toolkit.
• A monthly infusion of inspiration with my personal selection of quotes, books, and music.

Embrace the confluence of words and wonder, curated thoughtfully and sent straight to your inbox.

No fluff. Just the highest caliber of ideas.