Remove Duplicate From Linked-List

A corgi smiling happily

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

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

Sample Output

11 -> 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

1// This is an input class. Do not edit.
2class LinkedList {
3 constructor(value) {
4 this.value = value;
5 this.next = null;
6 }
7}
8
9function removeDuplicatesFromLinkedList(linkedList) {
10 let currentNode = linkedList
11 while(currentNode) {
12 let nextNode = currentNode.next
13 while (nextNode !== null && currentNode.value == nextNode.value) {
14 nextNode = nextNode.next
15 }
16
17 currentNode.next = nextNode
18 currentNode = nextNode
19 }
20
21 return linkedList;
22}
23
24/*
25
26{
27 "linkedList": {
28 "head": "1",
29 "nodes": [
30 {"id": "1", "next": "1-2", "value": 1},
31 {"id": "1-2", "next": "1-3", "value": 1},
32 {"id": "1-3", "next": "2", "value": 1},
33 {"id": "2", "next": "3", "value": 3},
34 {"id": "3", "next": "3-2", "value": 4},
35 {"id": "3-2", "next": "3-3", "value": 4},
36 {"id": "3-3", "next": "4", "value": 4},
37 {"id": "4", "next": "5", "value": 5},
38 {"id": "5", "next": "5-2", "value": 6},
39 {"id": "5-2", "next": null, "value": 6}
40 ]
41 }
42}
43
441, 1, 1, 3, 4, 4, 4, 5, 6, 6
45
46currentNode nextNode nexterNode
471 1 1
48
49*/

🦜

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 🙏

Subscribe to my newsletter

Get email from me about my ideas, full-stack development resources, tricks and tips as well as exclusive previews of upcoming articles.

No spam. Just the highest quality ideas you’ll find on the web.