Problem Description

You are given the head of a sorted linked list. Your task is to remove all duplicate values from the list so that each element appears only once. The linked list should remain sorted after removing duplicates.

The input is a linked list that is already sorted in ascending order. You need to traverse through the list and whenever you find consecutive nodes with the same value, you should keep only one occurrence and remove the others.

For example:

• If the input list is 1 -> 1 -> 2, the output should be 1 -> 2
• If the input list is 1 -> 1 -> 2 -> 3 -> 3, the output should be 1 -> 2 -> 3

The solution uses a single pointer cur to traverse the linked list. At each step, it checks if the current node's value equals the next node's value. If they are equal, it skips the next node by updating the next pointer to cur.next.next. If they are different, it simply moves to the next node. This approach efficiently removes duplicates in a single pass through the list with O(n) time complexity and O(1) space complexity.

Intuition

Since the linked list is already sorted, all duplicate values will appear consecutively. This is the key insight that makes the problem straightforward to solve.

Think about walking through a sorted list like 1 -> 1 -> 2 -> 3 -> 3. When we're at the first 1, we can immediately see that the next node also contains 1. Since we want to keep only one occurrence, we can simply skip over the duplicate by making our current node point directly to the node after the duplicate.

The natural approach is to use a single pointer to traverse the list. At each node, we ask: "Is my next neighbor the same as me?" If yes, we bypass that neighbor by connecting directly to the neighbor's next node (cur.next = cur.next.next). If no, we know we've found a unique value and can safely move forward.

This works because:

1. The sorted nature guarantees all duplicates are adjacent
2. We only need to look one step ahead to detect duplicates
3. By modifying the next pointers as we go, we can remove duplicates in-place without needing extra space

The beauty of this solution lies in its simplicity - we're essentially "short-circuiting" the list whenever we spot a duplicate, creating a direct path that skips over repeated values. We continue this process until we've examined every node, resulting in a clean list with no duplicates.

Learn more about Linked List patterns.

Solution Approach

We implement a single-pass traversal using a pointer cur that starts at the head of the linked list. The algorithm works as follows:

1. Initialize the traversal: Set cur = head to start from the beginning of the linked list.

2. Iterate through the list: Use a while loop that continues as long as both cur and cur.next exist. We need both conditions because:

   • We need cur to be valid to access its value
   • We need cur.next to be valid to compare with the current node

3. Check for duplicates: At each node, compare cur.val with cur.next.val:

   • If they are equal (cur.val == cur.next.val): We've found a duplicate. Skip the next node by setting cur.next = cur.next.next. This effectively removes the duplicate node from the list. Note that we don't move cur forward yet because there might be more duplicates of the same value.

   • If they are different: No duplicate found at this position. Move the pointer forward by setting cur = cur.next to continue checking the rest of the list.

4. Return the result: After the loop completes, return head which still points to the beginning of the now-deduplicated list.

The key insight is that when we find a duplicate, we stay at the current node and keep removing subsequent duplicates until we find a different value. Only then do we move forward. This ensures we handle cases where there are multiple consecutive duplicates (like 1 -> 1 -> 1 -> 2).

Time Complexity: O(n) where n is the number of nodes, as we visit each node exactly once.

Space Complexity: O(1) as we only use a single pointer variable and modify the list in-place.

Example Walkthrough

Let's walk through the solution with the linked list: 1 -> 1 -> 2 -> 3 -> 3

Initial State:

head -> [1] -> [1] -> [2] -> [3] -> [3] -> null
         ^
        cur

Step 1:

• cur points to first node (value = 1)
• Compare cur.val (1) with cur.next.val (1)
• They're equal, so skip the duplicate: cur.next = cur.next.next

head -> [1] -> [2] -> [3] -> [3] -> null
         ^
        cur

Step 2:

• cur still points to first node (value = 1)
• Compare cur.val (1) with cur.next.val (2)
• They're different, so move forward: cur = cur.next

head -> [1] -> [2] -> [3] -> [3] -> null
                ^
               cur

Step 3:

• cur points to node with value 2
• Compare cur.val (2) with cur.next.val (3)
• They're different, so move forward: cur = cur.next

head -> [1] -> [2] -> [3] -> [3] -> null
                       ^
                      cur

Step 4:

• cur points to first node with value 3
• Compare cur.val (3) with cur.next.val (3)
• They're equal, so skip the duplicate: cur.next = cur.next.next

head -> [1] -> [2] -> [3] -> null
                       ^
                      cur

Step 5:

• cur points to node with value 3
• cur.next is null, so the loop terminates

Final Result: 1 -> 2 -> 3

The algorithm successfully removed all duplicates while maintaining the sorted order. Notice how when we found duplicates (steps 1 and 4), we stayed at the current node and modified the links, but when values were different (steps 2 and 3), we moved the pointer forward.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the linked list. The algorithm traverses the linked list exactly once using a single while loop. In each iteration, it either removes a duplicate node (by adjusting the next pointer) or moves to the next node. Even when removing duplicates, each node is visited at most once, resulting in linear time complexity.

Space Complexity: O(1). The algorithm uses only a constant amount of extra space. It modifies the linked list in-place by adjusting pointers and only uses one additional variable cur to track the current position in the list. No additional data structures are created that scale with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Moving the pointer too early when handling multiple consecutive duplicates

The Problem: A common mistake is to always move the current pointer forward after removing a duplicate, like this:

while current and current.next:
    if current.val == current.next.val:
        current.next = current.next.next
        current = current.next  # WRONG: Moving forward too early!
    else:
        current = current.next

This fails when there are more than two consecutive duplicates. For example, with the list 1 -> 1 -> 1 -> 2, after removing the first duplicate, we'd have 1 -> 1 -> 2. But if we move current forward, we'd skip checking the new current.next, leaving a duplicate in the final result.

The Solution: Keep the current pointer at the same position after removing a duplicate. Only move forward when the current value differs from the next value:

while current and current.next:
    if current.val == current.next.val:
        current.next = current.next.next
        # Don't move current here - stay to check for more duplicates
    else:
        current = current.next  # Only move when values are different

Pitfall 2: Not checking for null pointers properly

The Problem: Checking only current without checking current.next can lead to a NullPointerException:

while current:  # Missing current.next check
    if current.val == current.next.val:  # current.next might be None!
        current.next = current.next.next

The Solution: Always check both current and current.next in the loop condition:

while current and current.next:  # Both checks are necessary
    if current.val == current.next.val:
        current.next = current.next.next

Pitfall 3: Forgetting to handle edge cases

The Problem: Not considering special cases like:

• Empty list (head = None)
• Single node list
• List with all identical values

The Solution: The algorithm naturally handles these cases:

• Empty list: The while loop never executes, returns None
• Single node: current.next is None, loop never executes, returns the single node
• All identical: The algorithm keeps the first occurrence and removes all others

The beauty of the solution is that these edge cases don't require special handling - the main logic covers them all.