This problem requires traversing a sorted linked list and removing consecutive duplicate nodes in place. The key is to adjust the next pointers carefully without losing any distinct nodes. By iterating through each node and skipping duplicates, the algorithm ensures the resulting list contains only unique values while preserving the original order.
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.
How GhostInterview Helps
- Highlights exact pointer manipulation needed to skip duplicates efficiently.
- Identifies potential failure modes like losing nodes when skipping duplicates.
- Provides step-by-step reasoning tied to linked-list traversal patterns for interview readiness.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Remove Duplicates from Sorted List instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Remove Duplicates from Sorted List from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Remove duplicates from a sorted linked list, leaving only distinct values, and return the modified list in sorted order.
Open problem page#86 Partition ListPartition a linked list such that all nodes less than x come before nodes greater than or equal to x while preserving relative order.
Open problem page#92 Reverse Linked List IIReverse a segment of a singly linked list from position left to right using precise pointer manipulation techniques.
Open problem page