Solution: Remove Duplicates from Sorted List

Let's solve the Remove Duplicates from Sorted List problem using the In-Place Manipulation of a Linked List pattern.

We'll cover the following

Statement

Given the head of a sorted linked list, remove all duplicates such that each element appears only once, and return the list in sorted order.

Constraints:

  • 0≤0 \leq n ≤300\leq 300, where n is the number of nodes in the list.

  • −100≤-100 \leq Node.data ≤100\leq 100

  • The list is guaranteed to be sorted in ascending order.

Solution

A key point that will help us solve this problem is that the linked list is sorted so that all duplicates will appear consecutively. This allows us to easily identify duplicates by comparing each node with its next node. We can use and manipulate the pointers to modify the original list directly in a single pass.

The solution works as follows:

  • The current pointer is initialized to the head of the linked list, which will allow traversal through the list.

  • Traverse the linked list to look for duplicates. Before updating the pointer to move to the next node, ensure that both current and current->next are not nullptr. The process is as follows:

    • If the current node's value is the same as the next node's, i.e., current->data ==== current->next->data, a duplicate is detected. Remove this duplicate by skipping the next node, i.e., by setting the current->next to current->next->next.

    • If the current node and the next node have different values, there are no duplicates, so move to the next node by setting current to current->next.

  • Continue this process until either current or current->next is nullptr, at which point the end of the list has been reached. Return the modified head of the list.

Why does the solution work?

One might wonder how skipping a node during traversal removes it from the actual list. When we assign current = head, we're setting current to refer to the same memory location as the node head. Therefore, any changes made to the node that current points to will reflect in the actual list.

The expression current->next = current->next->next modifies the next pointer of the node that the current points to. This means we're telling the node currently pointed to by current to skip over the duplicate node and point to the next one. By doing this, we're altering the connections in the linked list itself.

Let’s look at the following illustration to get a better understanding of the solution:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.