Remove Duplicates From Sorted Linked List

Removing duplicates from a sorted linked list is a common problem in data structures. The goal is to modify the list so that each element appears only once while maintaining the order. This problem is frequently asked in coding interviews and is essential for understanding linked list manipulation.

Understanding the Problem

Given a sorted singly linked list, remove all duplicates so that each element appears only once. The function should modify the list in place and return the new head of the modified list.

Example 1

Input: 1 → 1 → 2
Output: 1 → 2

Example 2

Input: 1 → 1 → 2 → 3 → 3
Output: 1 → 2 → 3

Approach to Solve the Problem

Since the linked list is already sorted, duplicate elements will always be adjacent. The best way to remove them is to iterate through the list and compare each node with the next node. If they are the same, update the pointer to skip the duplicate node.

Optimal Approach (Iterative Method)

1. Start from the head node and traverse the list.
2. Compare the current node with the next node:
   • If they are the same, update the next pointer to skip the duplicate.
   • If they are different, move to the next node.
3. Continue this process until the end of the list.

This method ensures that we only traverse the list once, resulting in O(n) time complexity and O(1) space complexity.

Python Implementation

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef removeDuplicates(head):current = headwhile current and current.next:if current.val == current.next.val:current.next = current.next.next  # Skip duplicate nodeelse:current = current.next  # Move to next nodereturn head  # Return modified linked list

Step-by-Step Explanation of the Code

1. Initialize current as the head of the linked list.
2. Traverse the list:
   • If current.val == current.next.val, we skip the duplicate by updating current.next.
   • Otherwise, we move to the next node.
3. Return the modified list after removing all duplicates.

Time and Space Complexity Analysis

✅ Time Complexity: O(n) – We traverse the linked list only once.
✅ Space Complexity: O(1) – No additional data structures are used; the list is modified in place.

Java Implementation

class ListNode {int val;ListNode next;ListNode(int val) {this.val = val;this.next = null;}}class Solution {public ListNode removeDuplicates(ListNode head) {ListNode current = head;while (current != null && current.next != null) {if (current.val == current.next.val) {current.next = current.next.next; // Skip duplicate} else {current = current.next;}}return head; // Return modified list}}

Explanation:

• We use a while loop to traverse the list.
• If a duplicate is found, we update the next pointer to skip it.
• If no duplicate is found, we move to the next node.
• This ensures all duplicates are removed efficiently.

C++ Implementation

struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}};class Solution {public:ListNode* removeDuplicates(ListNode* head) {ListNode* current = head;while (current && current->next) {if (current->val == current->next->val) {current->next = current->next->next; // Skip duplicate} else {current = current->next;}}return head;}};

Recursive Approach

An alternative way to solve this problem is recursion. This method is useful for understanding recursion, though it has a higher space complexity due to function call stacks.

Python Recursive Implementation

def removeDuplicatesRecursive(head):if not head or not head.next:return head  # Base case: If list is empty or has only one nodehead.next = removeDuplicatesRecursive(head.next)  # Recursive callreturn head.next if head.val == head.next.val else head

How the Recursive Method Works

1. Base Case: If the list is empty or has only one node, return head.
2. Recursive Call: Process the remaining list recursively.
3. Check for Duplicates:
   • If head.val == head.next.val, skip the duplicate.
   • Otherwise, keep the current node.

Downside: O(n) space complexity due to recursion stack.

Edge Cases to Consider

1. Empty List: None → Output: None
2. Single Element List: 5 → Output: 5
3. All Unique Elements: 1 → 2 → 3 → 4 → Output remains the same.
4. All Duplicates: 7 → 7 → 7 → 7 → Output: 7
5. Mixed Cases: 1 → 1 → 2 → 3 → 3 → 4 → 4 → 5 → Output: 1 → 2 → 3 → 4 → 5

Handling Variations of the Problem

1. Removing Duplicates in an Unsorted Linked List
   • Use a hash set to track unique values.
   • Iterate through the list, removing duplicates as needed.
2. Removing All Occurrences of Duplicates
   • Instead of keeping one occurrence, remove all duplicate values.
   • Requires an extra pointer to track the previous node.
3. Doubly Linked List
   • Similar approach but requires updating prev pointers.

Key Takeaways

✅ Two-pointer method is the optimal solution (O(n) time, O(1) space).
✅ Modify the list in place without extra memory.
✅ Recursive method is an alternative, but uses extra space.
✅ Works for all edge cases, including empty and fully unique lists.

By following this method, you can efficiently solve Remove Duplicates from Sorted Linked List on coding platforms and interviews.