Remove Duplicates from Sorted List

📋

Problem

Imagine cleaning up a sorted guest list where duplicate names appear consecutively, and you want to keep only unique entries without creating a new list.

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

The number of nodes in the list is in the range [1, 10^5].The list is sorted in non-decreasing order.Node values are integers.

Edge cases: Single node list → output is the same single node listAll nodes have the same value → output is a single node with that valueNo duplicates in the list → output is the same as input

</>

IDE

def deleteDuplicates(head: ListNode) -> ListNode:public ListNode deleteDuplicates(ListNode head)ListNode* deleteDuplicates(ListNode* head)function deleteDuplicates(head)

def deleteDuplicates(head):
    # Write your solution here
    pass

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        // Write your solution here
        return head;
    }
}

#include <vector>
using namespace std;

ListNode* deleteDuplicates(ListNode* head) {
    // Write your solution here
    return head;
}

function deleteDuplicates(head) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1,1,2]Duplicates not removed because next pointers were not updated when duplicate values found.✅ Inside the loop, when current.next.val == current.val, set current.next = current.next.next to unlink duplicates.

Wrong: [5,5,5,5,5]Code does not handle multiple consecutive duplicates correctly, leaving all duplicates intact.✅ Use a while loop to unlink all consecutive duplicates: while current.next and current.next.val == current.val: current.next = current.next.next

Wrong: [] or null on single node inputCode incorrectly removes or returns null for single node list.✅ Add a check to return head immediately if head.next is null or list length is 1.

Wrong: [1,1,2,3,3,4,5,5,5,6]Only first duplicate in each group removed, leaving some duplicates behind.✅ Loop to unlink all duplicates for each value before moving current pointer.

Wrong: Timeout or crash on large inputSolution uses nested loops or recursion causing O(n^2) or stack overflow.✅ Implement iterative single pass approach with O(n) time complexity.

✓

Test Cases

Now that basics work, test your code on empty and single-node lists to handle edge cases.

Try inputs with multiple duplicate groups to catch subtle bugs in your logic.

Optimize your solution to run efficiently on large inputs within time limits.

t1_01basic

Input{"head":[1,1,2]}

Expected[1,2]

⏱ Performance - must finish in 2000ms

The duplicate '1' is removed, leaving only one '1' followed by '2'.

💡 Traverse the list once, comparing current node with next node.

💡 Skip nodes whose values equal the current node's value to remove duplicates.

💡 Set current.next to current.next.next when duplicates are found to unlink them.

Why it failed: Output includes duplicates because next pointers were not updated correctly. Fix by setting current.next = current.next.next when duplicate values are detected.

✓ Duplicates removed correctly in a single pass.

t1_02basic

Input{"head":[1,2,2,3,4,4,4,5]}

Expected[1,2,3,4,5]

⏱ Performance - must finish in 2000ms

Duplicates '2' and '4' are removed, leaving unique sorted values.

💡 Check each node's value against the next node's value while traversing.

💡 Use a single pointer to skip over all consecutive duplicates.

💡 Update current.next to the first node with a different value.

Why it failed: Duplicates remain because loop does not skip all consecutive duplicates. Fix by looping while next node value equals current node value and unlinking them.

✓ All duplicates removed correctly in one traversal.

t2_01edge

Input{"head":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty list input returns empty list output.

💡 Check if head is null before processing.

💡 Return head immediately if list is empty.

💡 Avoid dereferencing null pointers in empty list.

Why it failed: Code crashes or returns non-empty output on empty input. Fix by adding a null check at start: if head is None return head.

✓ Handles empty list input gracefully.

t2_02edge

Input{"head":[7]}

Expected[7]

⏱ Performance - must finish in 2000ms

Single node list returns the same single node list.

💡 Single node list has no duplicates by definition.

💡 Ensure code does not remove or alter single node.

💡 Return head as is if next is null.

Why it failed: Single node list altered or removed incorrectly. Fix by ensuring loop condition handles single node and does not remove it.

✓ Single node list returned unchanged.

t2_03edge

Input{"head":[5,5,5,5,5]}

Expected[5]

⏱ Performance - must finish in 2000ms

All nodes have the same value; output is a single node with that value.

💡 Multiple consecutive duplicates should be skipped until a different value or end.

💡 Loop while next node value equals current node value and unlink duplicates.

💡 Result list contains only one node with the repeated value.

Why it failed: Output contains multiple duplicates instead of one node. Fix by looping to unlink all duplicates of the same value.

✓ All duplicates collapsed to single node correctly.

t3_01corner

Input{"head":[1,1,2,3,3,4,5,5,5,6]}

Expected[1,2,3,4,5,6]

⏱ Performance - must finish in 2000ms

Multiple groups of duplicates removed correctly.

💡 Check that all consecutive duplicates are removed, not just first occurrence.

💡 Ensure inner loop or repeated checks unlink all duplicates for each value.

💡 Update current.next repeatedly until next node value differs.

Why it failed: Only first duplicate in each group removed, leaving some duplicates. Fix by looping to unlink all duplicates for each value before moving current.

✓ All duplicate groups fully removed.

t3_02corner

Input{"head":[1,2,3,4,5]}

Expected[1,2,3,4,5]

⏱ Performance - must finish in 2000ms

No duplicates present; output same as input.

💡 Verify code does not remove unique nodes mistakenly.

💡 Check that current pointer advances correctly when no duplicates.

💡 Return original list unchanged if no duplicates found.

Why it failed: Unique nodes removed or list altered incorrectly. Fix by only unlinking nodes when next.val == current.val.

✓ Unique list returned unchanged.

t3_03corner

Input{"head":[1,1,1,2,2,3,3,3,3,4,5,5]}

Expected[1,2,3,4,5]

⏱ Performance - must finish in 2000ms

Long sequences of duplicates removed correctly.

💡 Handle long runs of duplicates by looping until next node value differs.

💡 Avoid off-by-one errors that leave duplicates at end of runs.

💡 Update current.next pointer carefully to skip all duplicates.

Why it failed: Duplicates remain at ends of runs due to off-by-one errors. Fix by careful loop condition: while current.next and current.next.val == current.val unlink.

✓ Long duplicate runs removed fully.

t4_01performance

Input{"head":[1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,25,25,26,26,27,27,28,28,29,29,30,30,31,31,32,32,33,33,34,34,35,35,36,36,37,37,38,38,39,39,40,40,41,41,42,42,43,43,44,44,45,45,46,46,47,47,48,48,49,49,50,50,51,51,52,52,53,53,54,54,55,55,56,56,57,57,58,58,59,59,60,60,61,61,62,62,63,63,64,64,65,65,66,66,67,67,68,68,69,69,70,70,71,71,72,72,73,73,74,74,75,75,76,76,77,77,78,78,79,79,80,80,81,81,82,82,83,83,84,84,85,85,86,86,87,87,88,88,89,89,90,90,91,91,92,92,93,93,94,94,95,95,96,96,97,97,98,98,99,99,100,100]}

Expectednull

⏱ Performance - must finish in 2000ms

n=200 nodes with duplicates in pairs; O(n) solution must complete within 2 seconds.

💡 Use a single pass to remove duplicates in O(n) time.

💡 Avoid nested loops or recursion that increase time complexity.

💡 Update pointers in-place without extra space.

Why it failed: Solution times out due to O(n^2) or recursive overhead. Fix by implementing iterative single pass with pointer updates.

✓ Solution runs in O(n) time confirming optimal complexity.

Practice

1. You are given a pointer to a node in a singly linked list, but you do not have access to the head of the list. You need to delete this node from the list in-place. Which approach guarantees an optimal solution for this problem?

easy

A. Copy the data from the next node into the current node, then delete the next node.

B. Mark the node as deleted and skip it during traversal without modifying pointers.

C. Use a recursive function to traverse and delete the node starting from the given node.

D. Traverse from the head node to find the previous node and update its next pointer.

Solution

1. Step 1: Understand the problem constraints

   We only have access to the node to delete, not the head, so traversing from head is impossible.

2. Step 2: Identify the approach that works without head

   Copying the next node's data into the current node and deleting the next node effectively removes the current node's value and maintains list integrity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Deleting without head requires copying next node's data [OK]

Hint: Deleting without head requires copying next node's data [OK]

Common Mistakes:

• Trying to delete by setting node to null without updating pointers
• Attempting to traverse from head when head is not given
• Marking node deleted without pointer updates

2. You are given a singly linked list and need to determine if it reads the same forwards and backwards without using extra space proportional to the list size. Which approach best guarantees an optimal solution in terms of time and space complexity?

easy

A. Convert the linked list to an array and check if the array is a palindrome.

B. Use a dynamic programming approach to store palindrome states for sublists.

C. Use a recursive two-pointer technique that compares nodes from front and back simultaneously.

D. Use a greedy approach by comparing nodes pairwise from start and end without recursion or extra space.

Solution

1. Step 1: Understand the problem constraints

   The problem requires checking palindrome property in a linked list without using extra space proportional to the list size, ruling out array conversion.

2. Step 2: Analyze space and time complexity of options

   Convert the linked list to an array and check if the array is a palindrome. uses O(n) extra space for array; Use a dynamic programming approach to store palindrome states for sublists. uses O(n^2) time and space; Use a recursive two-pointer technique that compares nodes from front and back simultaneously. uses O(n) time but O(n) space due to recursion stack; Use a greedy approach by comparing nodes pairwise from start and end without recursion or extra space. uses O(n) time and O(1) space by reversing the second half and comparing.

3. Step 3: Identify optimal approach

   Use a greedy approach by comparing nodes pairwise from start and end without recursion or extra space. is optimal with O(n) time and O(1) space, meeting constraints without recursion overhead.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Greedy pairwise comparison with in-place reversal is optimal [OK]

Hint: In-place reversal of second half achieves O(1) space palindrome check [OK]

Common Mistakes:

• Assuming recursion uses no extra space
• Confusing DP with palindrome linked list
• Thinking array conversion is space optimal

3. Given the following Python code implementing the recursive reversal of a sublist, what is the output when reversing positions 2 to 3 of the list [1, 2, 3, 4]?

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

successor = None

def reverseN(head, n):
    global successor
    if n == 1:
        successor = head.next
        return head
    last = reverseN(head.next, n - 1)
    head.next.next = head
    head.next = successor
    return last

def reverseBetween(head, left, right):
    if left == 1:
        return reverseN(head, right)
    head.next = reverseBetween(head.next, left - 1, right - 1)
    return head

# Build list
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(3):
    nodes[i].next = nodes[i+1]

new_head = reverseBetween(nodes[0], 2, 3)
curr = new_head
while curr:
    print(curr.val, end=' ')
    curr = curr.next

easy

A. 1 3 2 4

B. 1 2 3 4

C. 3 2 1 4

D. 1 4 3 2

Solution

1. Step 1: Trace reverseN for n=2 starting at node with val=2

   reverseN reverses first 2 nodes starting at node 2: it recursively reverses node 3, then sets pointers to reverse links between 2 and 3.

2. Step 2: Reconnect reversed sublist to original list

   Node 1 points to reversed sublist head (node 3), and the tail of reversed sublist (node 2) points to node 4.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches expected partial reversal between positions 2 and 3 [OK]

Hint: Partial reversal swaps nodes 2 and 3 only [OK]

Common Mistakes:

• Assuming full list reversed
• Off-by-one error reversing wrong nodes
• Confusing node values with positions

4. Consider the following code snippet implementing the optimal iterative approach to reverse nodes in k-groups. Given the linked list 1 -> 2 -> 3 -> 4 and k = 2, what is the value of group_prev.next.val after the first reversal group is processed inside the while loop?

easy

A. 1

B. 4

C. 2

D. 3

Solution

1. Step 1: Trace the first group reversal with k=2 on list 1 -> 2 -> 3 -> 4

   The first group is nodes with values 1 and 2. Reversing them results in 2 -> 1.

2. Step 2: Identify group_prev.next after reversal

   After reversal, group_prev.next points to the new head of the reversed group, which is node with value 2.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   First group's head after reversal is 2 [OK]

Hint: After reversal, group_prev.next points to new group's head [OK]

Common Mistakes:

• Assuming group_prev.next still points to original head (1)
• Confusing tail and head pointers after reversal

5. Identify the bug in the following tail-recursive reversal code snippet:

def reverseList(head):
    def helper(prev, curr):
        if not curr:
            return prev
        curr.next = prev
        next_temp = curr.next
        return helper(curr, next_temp)
    return helper(None, head)

medium

A. Line 3: Base case should check if prev is None instead of curr.

B. Line 6: The recursive call should pass next_temp as prev instead of curr.

C. Line 5: next_temp is assigned after curr.next is changed, losing original next node.

D. Line 2: The helper function should be iterative, not recursive.

Solution

1. Step 1: Analyze pointer updates

   Line 5 assigns next_temp = curr.next after curr.next is set to prev, so next_temp points to prev, not the original next node.

2. Step 2: Consequence of bug

   Because next_temp is incorrect, recursion loses the rest of the list, causing incomplete reversal or infinite loops.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Saving next node before pointer reversal is critical [OK]

Hint: Always save next node before changing curr.next [OK]

Common Mistakes:

• Swapping order of pointer updates
• Forgetting to set head.next to None in recursion