LeetCode 83 - Remove Duplicates from Sorted List

This problem asks us to remove duplicate values from a sorted singly linked list so that every distinct value appears exactly once.

leetcodeeasylinked-list

LeetCode Problem 83

Difficulty: 🟢 Easy
Topics: Linked List

Solution

Problem Understanding

This problem asks us to remove duplicate values from a sorted singly linked list so that every distinct value appears exactly once. The important detail is that the linked list is already sorted in ascending order, which makes duplicate detection much easier than in an unsorted list.

The input is the head of a singly linked list. Each node contains an integer value and a pointer to the next node. Because the list is sorted, duplicate values always appear next to each other. For example, if the list is:

1 -> 1 -> 2 -> 3 -> 3

the duplicate 1 values are consecutive, and the duplicate 3 values are also consecutive.

The expected output is the same linked list structure, modified so that duplicate nodes are removed while maintaining the sorted order. For the previous example, the result becomes:

1 -> 2 -> 3

The constraints tell us several useful things about the input:

  • The number of nodes ranges from 0 to 300, meaning the list can be empty.
  • Node values range between -100 and 100, but since the list is sorted, the specific value range is not particularly important for the solution.
  • The sorted guarantee is the key property that allows an efficient solution.

Since duplicates in a sorted list are always adjacent, we never need to search the entire list to determine whether a value has already appeared. We only need to compare a node with its immediate next node.

There are several important edge cases to consider upfront. The list might be empty (head = None), in which case there is nothing to remove. The list might contain only one node, which is already unique. All nodes might be identical, such as [1,1,1,1], requiring repeated duplicate removals. Another tricky case is when no duplicates exist at all, such as [1,2,3], where the list should remain unchanged.

Approaches

Brute Force Approach

A brute force solution would ignore the fact that the list is sorted and instead track previously seen values using an auxiliary data structure such as a hash set.

We would iterate through the linked list node by node. For each node, we would check whether its value already exists in a set. If the value has been seen before, we remove the node by adjusting pointers. Otherwise, we insert the value into the set and continue traversing.

This approach produces the correct answer because every value is checked against all previously encountered values. Duplicate nodes are removed while unique values are preserved.

However, this method uses extra memory unnecessarily. Since the list is already sorted, duplicate values are adjacent, meaning a set is overkill. We can solve the problem more efficiently in terms of space by exploiting the sorted property.

Optimal Approach

The key insight is that because the linked list is sorted, duplicate values always appear consecutively.

Instead of remembering every value we have seen, we only need to compare the current node with the next node:

  • If both values are the same, the next node is a duplicate and should be skipped.
  • If the values are different, we move forward to the next node.

This works because sorting guarantees that once we move past a value, we will never encounter it again later in the list.

By simply modifying pointers in place, we can remove duplicates in a single traversal while using constant extra space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Uses a hash set to track seen values
Optimal O(n) O(1) Traverses once and removes duplicates in place

Algorithm Walkthrough

Optimal Algorithm

  1. Start with a pointer called current at the head of the linked list.
  2. Continue traversing while both current and current.next exist. We need current.next because duplicate checking happens by comparing neighboring nodes.
  3. Compare current.val with current.next.val.
  4. If the values are equal, a duplicate has been found. Remove the duplicate node by changing:

current.next = current.next.next

This skips over the duplicate node and reconnects the list. 5. Do not move the current pointer immediately after removing a duplicate. This is important because there may be multiple duplicates in a row, such as:

1 -> 1 -> 1 -> 2

After removing one duplicate, we still need to compare the same node again. 6. If the values are different, move current to the next node because the current value is already unique. 7. Continue until the end of the list is reached. 8. Return the original head, since the list has been modified in place.

Why it works

The correctness of this algorithm relies on the sorted property of the linked list. Since identical values always appear consecutively, comparing adjacent nodes is sufficient to detect duplicates. At every step, the algorithm maintains the invariant that all nodes before current are already duplicate free. By removing duplicates immediately when found, the final linked list contains exactly one copy of each value.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        current = head

        while current and current.next:
            if current.val == current.next.val:
                current.next = current.next.next
            else:
                current = current.next

        return head

This implementation follows the optimal algorithm directly.

The variable current starts at the head of the linked list and moves through the list one node at a time. The loop condition checks both current and current.next because duplicate comparison requires access to neighboring nodes.

Inside the loop, the algorithm compares the current node value with the next node value. If they match, the duplicate node is removed by changing the next pointer. Specifically, current.next is reassigned to skip the duplicate node and point to the node after it.

Notice that after removing a duplicate, the algorithm does not move the current pointer. This ensures that consecutive duplicates are handled correctly.

If the values differ, the algorithm advances to the next node because the current node is already confirmed unique.

Finally, the method returns head, which now represents the modified duplicate free linked list.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
	current := head

	for current != nil && current.Next != nil {
		if current.Val == current.Next.Val {
			current.Next = current.Next.Next
		} else {
			current = current.Next
		}
	}

	return head
}

The Go implementation is almost identical to the Python version, but there are some language specific differences.

In Go, linked list nodes are pointers, so nil is used instead of Python's None. Field access uses capitalized names (Val and Next) because they match the provided struct definition.

The pointer manipulation logic remains exactly the same. Since Go uses explicit pointers, updating current.Next modifies the linked list in place without needing additional memory.

There are no concerns about integer overflow here because the algorithm only compares values and updates pointers.

Worked Examples

Example 1

Input: head = [1,1,2]

Initial list:

1 -> 1 -> 2

Step Current Node Next Node Action Resulting List
1 1 1 Duplicate found, skip next node 1 -> 2
2 1 2 Different values, move forward 1 -> 2
End 2 None Stop traversal 1 -> 2

Final output:

[1,2]

Example 2

Input: head = [1,1,2,3,3]

Initial list:

1 -> 1 -> 2 -> 3 -> 3

Step Current Node Next Node Action Resulting List
1 1 1 Duplicate found, remove duplicate 1 -> 2 -> 3 -> 3
2 1 2 Move forward 1 -> 2 -> 3 -> 3
3 2 3 Move forward 1 -> 2 -> 3 -> 3
4 3 3 Duplicate found, remove duplicate 1 -> 2 -> 3
End 3 None Stop traversal 1 -> 2 -> 3

Final output:

[1,2,3]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited at most once during traversal
Space O(1) Only a single pointer variable is used

The time complexity is O(n) because we traverse the linked list only once. Even when duplicates are removed, each node is processed a constant number of times.

The space complexity is O(1) because the algorithm modifies the linked list in place and uses only a single traversal pointer. No additional data structures are required.

Test Cases

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode()
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

def to_list(head):
    result = []

    while head:
        result.append(head.val)
        head = head.next

    return result

solution = Solution()

# Example 1
head = build_list([1, 1, 2])
assert to_list(solution.deleteDuplicates(head)) == [1, 2]  # basic duplicate removal

# Example 2
head = build_list([1, 1, 2, 3, 3])
assert to_list(solution.deleteDuplicates(head)) == [1, 2, 3]  # duplicates at multiple positions

# Empty list
head = build_list([])
assert to_list(solution.deleteDuplicates(head)) == []  # handles empty input

# Single node
head = build_list([5])
assert to_list(solution.deleteDuplicates(head)) == [5]  # single element remains unchanged

# No duplicates
head = build_list([1, 2, 3, 4])
assert to_list(solution.deleteDuplicates(head)) == [1, 2, 3, 4]  # already unique

# All duplicates
head = build_list([1, 1, 1, 1])
assert to_list(solution.deleteDuplicates(head)) == [1]  # repeated duplicate removal

# Negative numbers
head = build_list([-3, -3, -2, -1, -1])
assert to_list(solution.deleteDuplicates(head)) == [-3, -2, -1]  # negative values

# Duplicates at the end
head = build_list([1, 2, 3, 3])
assert to_list(solution.deleteDuplicates(head)) == [1, 2, 3]  # tail duplicate removal

# Duplicates at the beginning
head = build_list([1, 1, 2, 3])
assert to_list(solution.deleteDuplicates(head)) == [1, 2, 3]  # head duplicate removal
Test Why
[1,1,2] Verifies basic duplicate removal
[1,1,2,3,3] Tests duplicates in multiple regions
[] Ensures empty input works
[5] Confirms single node handling
[1,2,3,4] Verifies unchanged unique list
[1,1,1,1] Tests repeated consecutive duplicate removal
[-3,-3,-2,-1,-1] Validates negative values
[1,2,3,3] Ensures duplicates at tail are removed
[1,1,2,3] Ensures duplicates at head are removed

Edge Cases

One important edge case is an empty linked list. Since head can be None, attempting to access head.next without checking would cause an error. The implementation handles this safely because the loop condition checks whether current exists before accessing current.next.

Another important case is when multiple duplicates appear consecutively, such as [1,1,1,1]. A buggy implementation might move the pointer too early and miss some duplicates. This solution avoids that issue by keeping current in place after removing a duplicate, ensuring every adjacent duplicate is checked.

A third edge case occurs when the list already contains no duplicates, such as [1,2,3,4]. The implementation correctly leaves the list unchanged because each comparison finds different values, causing the pointer to simply move forward.

A final edge case is duplicates appearing at the beginning or end of the list. Removing nodes near boundaries can introduce pointer handling mistakes. Since this algorithm only adjusts current.next, it naturally handles duplicates at the head or tail without any special case logic.