Problem Statement:

Given a sorted linked list, remove all the duplicate elements to leave only distinct numbers. The linked list should remain sorted, and the modified list should be returned.

Examples

Example 1:

• Input: 1 -> 1 -> 2
• Output: 1 -> 2
• Justification: Since 1 is repeated, we remove the duplicate to leave a sorted list of unique numbers.

Example 2:

• Input: 1 -> 2 -> 2 -> 3
• Output: 1 -> 2 -> 3
• Justification: Here, 2 is the duplicate element, and by removing it, we obtain a list containing only distinct elements.

Example 3:

• Input: 3 -> 3 -> 3
• Output: 3
• Justification: We remove the repeated 3s to leave a single 3 in the list.

Constraints:

• The number of nodes in the list is in the range [0, 300].
• -100 <= Node.val <= 100
• The list is guaranteed to be sorted in ascending order.

Solution

To solve this problem, start at the beginning of the list. If the list is empty or has only one item, return the list. If not, look at each element in the list one by one. If two elements next to each other that are the same, skip over the second one. Do this by changing the link of the first element to the element after the second one. Keep doing this until you reach the end of the list. This way, all the repeated elements are removed, and you still keep the list in order.

Here is the step-by-step solution.

1. Start at the Head: Begin at the head of the linked list.

2. Check for Empty or Single-Node List:

   • If the list is empty or contains only one node, return the list as is, since there are no duplicates to remove.

3. Traversal:

   • Initialize a pointer, say current, to the head of the list.
   • While current and current.next are not null (ensuring there are at least two nodes to compare):
     • Check if current's value is equal to current.next's value.
       • If they are equal, it indicates a duplicate.
         • Update current.next to current.next.next. This skips over the duplicate node and effectively removes it from the list.
       • If they are not equal, move current to the next node (current = current.next). This step is crucial to progress through the list.

4. Final List:

   • Once the end of the list is reached (i.e., current or current.next becomes null), return the head of the modified list.

Algorithm Walkthrough:

• Start at the head of the linked list.
• For each node:
  • Compare the current node’s value with its successor.
  • If they are identical, remove the duplicate by updating the next pointer of the current node to its successor’s successor.
  • If they are distinct, move to the next node.
• Continue until the end of the list is reached.

Here is the visual representation of the algorithm: