Solution: Remove Duplicates from a Linked List

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.

• $0 \leq$ n $\leq 500$

• $-5 \times 10^3 \leq$ Node.value $\leq 5\times 10^3$

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:

1. If the list is empty, we return NULL.

2. If the list has only one node, we leave it unchanged and return the list.

3. Initialize the outer_node to the head of the list and iterate through each node of the list until the outer_node is not NULL.

   1. Initialize the inner_node to the current outer_node and iterate through each node of the list until the inner_node is not NULL.

      1. While iterating, check whether there is a node after inner_node:

         1. Verify if a duplicate node is detected by comparing the values of the outer_node and the node right after the inner_node. If they are equal, skip it by updating the reference of the inner_node to point directly to the node right after the duplicate one. This effectively removes the duplicate node from the list.

         2. Otherwise, point inner_node to the next node.

4. Return head of the modified list after removing duplicates.

Let’s look at the illustration below to better understand the solution: