Solution: Remove Duplicates from a Linked List
Let’s solve the Remove Duplicates from a Linked List problem.
We'll cover the following
Statement
Given the head
of a singly linked list, remove any duplicate nodes from the list in place, ensuring that only one occurrence of each value is retained in the modified list.
Constraints:
Let n
be the number of nodes in a linked list.
n
Node.value
Solution
In this solution, we traverse the list starting from the beginning to remove the duplicate nodes. We compare the value of each node with all subsequent nodes in the list. If a duplicate node is found, we skip it by updating the reference of the previous node to point directly to the node right after the duplicate one. This process is repeated for each node in the list, ensuring no duplicates remain. Finally, we return the modified list without any duplicate nodes.
Let’s walk through the steps of the solution:
If the list is empty, we return NULL.
If the list has only one node, we leave it unchanged and return the list.
Initialize the
outerNode
to thehead
of the list and iterate through each node of the list until theouterNode
is not NULL.Initialize the
innerNode
to the currentouterNode
and iterate through each node of the list until theinnerNode
is not NULL.While iterating, check whether there is a node after
innerNode
:Verify if a duplicate node is detected by comparing the values of the
outerNode
and the node right after theinnerNode
. If they are equal, skip it by updating the reference of theinnerNode
to point directly to the node right after the duplicate one. This effectively removes the duplicate node from the list.Otherwise, point
innerNode
to the next node.
Return
head
of the modified list after removing duplicates.
Let’s look at the illustration below to better understand the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.