Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.
Example 1:
Input: head = [1,2,3,3,4,4,5] Output: [1,2,5]
Example 2:
Input: head = [1,1,1,2,3] Output: [2,3]
Constraints:
[0, 300].-100 <= Node.val <= 100In #82 Remove Duplicates from Sorted List II, the linked list is already sorted, which means duplicate values appear consecutively. The challenge is not just removing extra copies but deleting all nodes that have duplicate values, leaving only nodes that appear exactly once.
A common strategy uses a dummy (sentinel) node and two pointers. One pointer tracks the last confirmed unique node, while another scans ahead to detect duplicate sequences. When a sequence of equal values is found, the algorithm skips the entire group instead of keeping one instance. If the value appears only once, it remains connected to the result list.
This approach works efficiently because the list is sorted, allowing duplicates to be detected in a single pass. Careful pointer updates ensure nodes are removed without breaking the list structure. The method processes each node at most once, leading to optimal performance.
Time Complexity: O(n) since the list is traversed once. Space Complexity: O(1) because only pointers are used without extra data structures.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Pointers with Dummy Node | O(n) | O(1) |
NeetCodeIO
In this approach, we'll use two pointers: prev and current. The prev pointer will be the last node in the result list without duplicates, and current pointer will traverse the input list. We initialize a dummy node before the head to simplify the edge case management when duplicates are at the start of the list.
While traversing, if the current node has the same value as the next node, we keep moving forward to skip all nodes with this value. If prev.next points to the current node when a duplicate sequence starts, we simply remove the sequence by connecting prev to the node after the last duplicate.
Time Complexity: O(n), where n is the number of nodes in the list, because each node is visited at most twice.
Space Complexity: O(1), as no additional space is used aside from a few pointers.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6
The C solution defines a ListNode structure to represent each node in the linked list. A dummy node is initialized with dummy.next pointing to head. Two pointers, prev and current, are used to traverse and modify the linked list to remove duplicates. The while loop ensures that all duplicates are detected and skipped over, while prev is maintained to ensure only distinct numbers are retained in the list.
This approach utilizes recursion to elegantly process the list for duplicates. The concept centers on calling a helper function that, at each level, processes the current node list by recursively evaluating burdens of duplicates. The recursion simplifies decision-making by naturally moving through the list and sorting out duplicate removal due to stack calls automatically handling execution follow-through.
Each call checks for duplicate patterns and recursively bridges connections between unique nodes. This allows the call stack to effectively tackle the transformation demands of duplicate filtering through returning modified structures created per recursion.
Time Complexity: O(n), visiting each node once recursively.
Space Complexity: O(n), accounting for call stack space in recursion.
1class ListNode:
2 def __init__(self, val=
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem frequently appear in technical interviews at top tech companies. It tests linked list manipulation, pointer control, and the ability to handle edge cases such as duplicates at the beginning or end of the list.
A dummy node simplifies edge cases, especially when the head of the list itself is part of a duplicate sequence. It provides a stable starting point so pointer adjustments remain consistent when removing nodes.
The optimal approach uses a dummy node and two-pointer technique. By scanning the sorted list and detecting groups of equal values, you can skip entire duplicate sequences while keeping only unique nodes. This allows the problem to be solved in a single pass with constant extra space.
The key concepts are linked list traversal and the two-pointer technique. Understanding how to manipulate node pointers safely and detect consecutive duplicates in a sorted structure is crucial for solving the problem efficiently.
The Python recursive solution systematically checks each node and its successively linked node's equality. When duplicates are found, the head progress skips them altogether, recursively pursuing a clean node linkage post-duplicate skipping.