Remove Duplicates from Sorted List - Video Solutions

Problem Overview: Given the head of a sorted linked list, remove duplicate nodes so each value appears only once. The list must remain sorted and you should return the modified head of the list.

The key detail is that the list is already sorted. That means duplicates always appear next to each other. Instead of storing values in a set or reordering nodes, you simply compare each node with its next neighbor and skip duplicates.

Approach 1: Iterative Two Pointers (O(n) time, O(1) space)

This approach walks through the linked list once using a pointer called current. Because the list is sorted, duplicate values will always appear consecutively. When current.val == current.next.val, you remove the duplicate by updating the pointer: current.next = current.next.next. Otherwise, move the pointer forward normally.

The algorithm performs a single pass through the list, comparing each node with the next node. No extra data structures are required, which keeps space usage constant. This pattern is closely related to the two pointers technique, where one pointer scans the list while conditionally adjusting the next reference. Time complexity is O(n) since every node is visited once, and space complexity is O(1) because the list is modified in place.

This is the most common and practical solution. It’s straightforward, efficient, and works well for long lists without risking stack overflow.

Approach 2: Recursive Approach (O(n) time, O(n) space)

The recursive solution processes the list from the front and lets recursion handle the rest of the nodes. If the current node has the same value as its next node, skip the duplicate by returning the recursive result of head.next. Otherwise, connect the current node to the processed remainder of the list using head.next = deleteDuplicates(head.next).

This approach naturally fits problems where the structure repeats itself at every node. Each recursive call processes one node and reduces the problem size by one element. The algorithm still visits each node once, giving O(n) time complexity. However, recursion adds call stack overhead, resulting in O(n) auxiliary space.

Recursion is clean and expressive, especially if you're comfortable with recursion patterns on linked lists. However, most production code prefers the iterative version because it avoids stack usage.

Recommended for interviews: The iterative two-pointer approach is the expected solution. It demonstrates that you recognize the sorted property and can modify a linked list in place with O(1) extra space. Mentioning recursion as an alternative shows deeper understanding, but the iterative method is usually what interviewers want to see first.