#83

Easy

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Remove Duplicates from Sorted List

Efficiently remove duplicates from a sorted linked list using precise pointer manipulation while maintaining node order integrity.

linked list

Problem Statement

You are given the head of a sorted singly linked list. Your task is to remove all duplicate nodes so that each value appears only once, ensuring the list remains sorted. Return the modified linked list after all duplicates have been removed.

For example, given head = [1,1,2], after removing duplicates the list should become [1,2]. Similarly, for head = [1,1,2,3,3], the resulting linked list should be [1,2,3]. The list may contain zero or more nodes, but it is always sorted in ascending order.

Examples

Example 1

Input: head = [1,1,2]

Output: [1,2]

Example details omitted.

Example 2

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

Output: [1,2,3]

Example details omitted.

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 Approach

Iterative Pointer Traversal

Initialize a current pointer at the head. Traverse the list, and whenever current.val equals current.next.val, skip the duplicate by setting current.next = current.next.next. Continue until the end of the list to remove all duplicates in one pass.

Recursive Removal

Define a recursive function that processes the list from head to tail. If the head is null or head.next is null, return head. Otherwise, recursively remove duplicates in the remainder of the list and adjust head.next to point to the processed sublist, skipping duplicate values as needed.

Edge Case Handling

Always check for null head or single-node lists. Ensure that consecutive duplicates at the start or end of the list are handled without breaking the pointer chain. Carefully update next pointers to prevent memory loss or skipped nodes.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each node is visited once. Space complexity is O(1) for iterative solutions and O(n) for recursive calls due to the call stack.

What Interviewers Usually Probe

Wants to see clear pointer updates and in-place modifications.
Checks for understanding of linked list traversal and duplicate detection.
May probe handling of empty lists or lists with all identical values.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check current.next before accessing its value can cause null pointer errors.
Incorrectly skipping nodes may remove distinct values along with duplicates.
Using extra data structures violates the O(1) space expectation for this problem.

Follow-up variants

Remove duplicates from a sorted doubly linked list.
Return the count of unique elements while modifying the list in place.
Allow at most two occurrences of each element instead of one.

FAQ

What is the main approach for Remove Duplicates from Sorted List?

Traverse the list with a pointer and remove consecutive duplicates by updating next pointers to skip them.

Can this problem be solved recursively?

Yes, a recursive approach processes the list from head to tail, skipping duplicates and adjusting next pointers.

What is the time and space complexity?

Time is O(n) since each node is visited once; space is O(1) iteratively and O(n) recursively due to call stack.

How do I handle edge cases like empty or single-node lists?

Check if head is null or head.next is null before processing; these cases require no changes.

Why is pointer manipulation crucial in this linked-list problem?

Incorrect pointer updates can lose nodes or fail to remove duplicates, so precise adjustments are essential.

terminal

Solution

Solution 1: Single Pass

We use a pointer $cur$ to traverse the linked list. If the element corresponding to the current $cur$ is the same as the element corresponding to $cur.next$, we set the $next$ pointer of $cur$ to point to the next node of $cur.next$. Otherwise, it means that the element corresponding to $cur$ in the linked list is not duplicated, so we can move the $cur$ pointer to the next node.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

# 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]:
        cur = head
        while cur and cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

Continue Practicing

#82 remove duplicates from sorted list ii #86 partition list #92 reverse linked list ii