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 outerNode to the head of the list and iterate through each node of the list until the outerNode is not NULL.

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

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

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

         2. Otherwise, point innerNode 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: