Remove Duplicates from Sorted List

🎯

Remove Duplicates from Sorted List

easyLINKED_LISTAmazonGoogleBloomberg

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.

💡 This problem is about modifying a linked list in place to remove duplicates. Beginners often struggle because they need to carefully manage pointers without losing parts of the list or creating new nodes.

📋

Problem Statement

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.

💡

Example

Input"head = [1,1,2]"

Output[1,2]

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

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

Output[1,2,3]

Duplicates '1' and '3' are removed, preserving one occurrence each.

• Single node list → output is the same single node list
• All nodes have the same value → output is a single node with that value
• No duplicates in the list → output is the same as input
• Empty list (head = null) → output is null

⚠️

Common Mistakes

Not updating the current pointer correctly after removing duplicates

Infinite loop or skipping nodes incorrectly

✅ Only move current pointer forward when no duplicate is removed

Failing to handle empty list or single node list

Null pointer exceptions or crashes

✅ Add base case checks for null or single node before processing

Creating new nodes instead of modifying in place

Extra space usage and slower performance

✅ Modify pointers to skip duplicates without creating new nodes

Not considering that the list is sorted

Unnecessary complexity or incorrect logic

✅ Use the sorted property to only compare adjacent nodes

🧠

Brute Force (Nested Loops)

💡 This approach exists to build intuition by explicitly checking every node against all others, showing why it's inefficient but conceptually simple.

Intuition

For each node, scan ahead to find and remove all duplicates by comparing values, removing nodes one by one.

Algorithm

1. Start from the head node.
2. For each node, use a nested loop to check subsequent nodes for duplicates.
3. If a duplicate is found, remove it by adjusting pointers.
4. Continue until the end of the list is reached.

💡 Nested loops make it easy to understand but inefficient; beginners often miss pointer updates inside nested loops.

</>

Code

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

def deleteDuplicates(head):
    current = head
    while current:
        runner = current
        while runner.next and runner.next.val == current.val:
            runner.next = runner.next.next
        current = current.next
    return head

# Driver code to test
if __name__ == '__main__':
    # Create linked list 1->1->2
    head = ListNode(1, ListNode(1, ListNode(2)))
    new_head = deleteDuplicates(head)
    # Print list
    curr = new_head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

Line Notes

current = headInitialize pointer to start traversing the list

while current:Outer loop to process each node one by one

runner = currentRunner pointer to check duplicates ahead of current

while runner.next and runner.next.val == current.val:Inner loop skips all nodes with duplicate values

runner.next = runner.next.nextRemove duplicate by skipping the node

current = current.nextMove to next distinct node

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public static ListNode deleteDuplicates(ListNode head) {
        ListNode current = head;
        while (current != null) {
            ListNode runner = current;
            while (runner.next != null && runner.next.val == current.val) {
                runner.next = runner.next.next;
            }
            current = current.next;
        }
        return head;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(1);
        head.next.next = new ListNode(2);
        ListNode newHead = deleteDuplicates(head);
        ListNode curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}

Line Notes

ListNode current = head;Start traversal from head

while (current != null)Process each node until end

ListNode runner = current;Runner to check duplicates ahead

while (runner.next != null && runner.next.val == current.val)Skip all duplicates after current

runner.next = runner.next.next;Remove duplicate node by pointer update

current = current.next;Move to next distinct node

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* deleteDuplicates(ListNode* head) {
    ListNode* current = head;
    while (current) {
        ListNode* runner = current;
        while (runner->next && runner->next->val == current->val) {
            runner->next = runner->next->next;
        }
        current = current->next;
    }
    return head;
}

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(1);
    head->next->next = new ListNode(2);
    ListNode* newHead = deleteDuplicates(head);
    ListNode* curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

Line Notes

ListNode* current = head;Initialize pointer to start list traversal

while (current)Outer loop to process each node

ListNode* runner = current;Runner pointer to find duplicates ahead

while (runner->next && runner->next->val == current->val)Skip all duplicates after current node

runner->next = runner->next->next;Remove duplicate by pointer adjustment

current = current->next;Advance to next distinct node

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function deleteDuplicates(head) {
    let current = head;
    while (current !== null) {
        let runner = current;
        while (runner.next !== null && runner.next.val === current.val) {
            runner.next = runner.next.next;
        }
        current = current.next;
    }
    return head;
}

// Test
const head = new ListNode(1, new ListNode(1, new ListNode(2)));
const newHead = deleteDuplicates(head);
let curr = newHead;
let output = '';
while (curr !== null) {
    output += curr.val + ' ';
    curr = curr.next;
}
console.log(output.trim());

Line Notes

let current = head;Start traversal from head node

while (current !== null)Process each node until list ends

let runner = current;Runner pointer to check duplicates ahead

while (runner.next !== null && runner.next.val === current.val)Skip all duplicate nodes after current

runner.next = runner.next.next;Remove duplicate by skipping node

current = current.next;Move to next distinct node

⏱

Complexity

TimeO(n)

SpaceO(1)

Each node is visited once by current pointer, and duplicates are skipped by runner pointer without extra space.

💡 For n=100, this means roughly 100 operations, which is efficient enough for large lists.

Interview Verdict: Accepted

This approach is efficient and accepted because it uses a single pass with constant space.

🧠

Recursive Approach

💡 Recursion helps understand the problem by breaking it down into smaller subproblems, though it uses call stack space.

Intuition

Recursively process the list, removing duplicates by comparing current node with the next node and skipping duplicates.

Algorithm

1. If the list is empty or has one node, return it.
2. Recursively call the function on the next node.
3. Compare current node's value with the returned list's head value.
4. If equal, skip current node by returning the next node; else link current node to returned list.

💡 Recursion can be tricky to visualize, especially how the call stack unwinds and links nodes.

</>

Code

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

def deleteDuplicates(head):
    if not head or not head.next:
        return head
    head.next = deleteDuplicates(head.next)
    if head.val == head.next.val:
        return head.next
    else:
        return head

# Driver code
if __name__ == '__main__':
    head = ListNode(1, ListNode(1, ListNode(2)))
    new_head = deleteDuplicates(head)
    curr = new_head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

Line Notes

if not head or not head.next:Base case: empty or single node list

head.next = deleteDuplicates(head.next)Recursively process the rest of the list

if head.val == head.next.val:Check if current node is duplicate of next

return head.nextSkip current node if duplicate

return headKeep current node if not duplicate

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;
        head.next = deleteDuplicates(head.next);
        if (head.val == head.next.val) return head.next;
        else return head;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(1);
        head.next.next = new ListNode(2);
        ListNode newHead = deleteDuplicates(head);
        ListNode curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}

Line Notes

if (head == null || head.next == null) return head;Base case for recursion

head.next = deleteDuplicates(head.next);Recursive call on next node

if (head.val == head.next.val) return head.next;Skip current node if duplicate

else return head;Keep current node if unique

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* deleteDuplicates(ListNode* head) {
    if (!head || !head->next) return head;
    head->next = deleteDuplicates(head->next);
    if (head->val == head->next->val) return head->next;
    else return head;
}

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(1);
    head->next->next = new ListNode(2);
    ListNode* newHead = deleteDuplicates(head);
    ListNode* curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

Line Notes

if (!head || !head->next) return head;Base case for recursion

head->next = deleteDuplicates(head->next);Recursive call on next node

if (head->val == head->next->val) return head->next;Skip current node if duplicate

else return head;Keep current node if unique

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function deleteDuplicates(head) {
    if (!head || !head.next) return head;
    head.next = deleteDuplicates(head.next);
    if (head.val === head.next.val) return head.next;
    else return head;
}

// Test
const head = new ListNode(1, new ListNode(1, new ListNode(2)));
const newHead = deleteDuplicates(head);
let curr = newHead;
let output = '';
while (curr !== null) {
    output += curr.val + ' ';
    curr = curr.next;
}
console.log(output.trim());

Line Notes

if (!head || !head.next) return head;Base case for recursion

head.next = deleteDuplicates(head.next);Recursive call on next node

if (head.val === head.next.val) return head.next;Skip current node if duplicate

else return head;Keep current node if unique

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is visited once, but recursion uses call stack proportional to list length.

💡 For n=100, this means 100 recursive calls, which can risk stack overflow in some languages.

Interview Verdict: Accepted

Accepted but less optimal due to recursion stack; good to mention but iterative preferred in interviews.

🧠

Iterative Single Pass (Optimal In-Place)

💡 This is the most efficient and clean approach, using a single pointer to skip duplicates in one pass without extra space.

Intuition

Since the list is sorted, duplicates appear consecutively. Move through the list once, linking each unique node to the next unique node.

Algorithm

1. Initialize a pointer at the head of the list.
2. While the pointer and its next node exist, compare their values.
3. If values are equal, skip the next node by adjusting pointers.
4. Otherwise, move the pointer forward.
5. Return the head of the modified list.

💡 This approach is straightforward but requires careful pointer updates to avoid losing nodes.

</>

Code

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

def deleteDuplicates(head):
    current = head
    while current and current.next:
        if current.val == current.next.val:
            current.next = current.next.next
        else:
            current = current.next
    return head

# Driver code
if __name__ == '__main__':
    head = ListNode(1, ListNode(1, ListNode(2)))
    new_head = deleteDuplicates(head)
    curr = new_head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

Line Notes

current = headStart pointer at head to traverse list

while current and current.next:Loop until end of list or last node

if current.val == current.next.val:Check if current and next node are duplicates

current.next = current.next.nextSkip duplicate node by pointer update

else:If not duplicate, move pointer forward

current = current.nextAdvance to next node

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public static ListNode deleteDuplicates(ListNode head) {
        ListNode current = head;
        while (current != null && current.next != null) {
            if (current.val == current.next.val) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }
        return head;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(1);
        head.next.next = new ListNode(2);
        ListNode newHead = deleteDuplicates(head);
        ListNode curr = newHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}

Line Notes

ListNode current = head;Initialize pointer at head

while (current != null && current.next != null)Traverse list until last node

if (current.val == current.next.val)Check for duplicate nodes

current.next = current.next.next;Remove duplicate by skipping node

elseIf no duplicate, move pointer forward

current = current.next;Advance pointer

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* deleteDuplicates(ListNode* head) {
    ListNode* current = head;
    while (current && current->next) {
        if (current->val == current->next->val) {
            current->next = current->next->next;
        } else {
            current = current->next;
        }
    }
    return head;
}

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(1);
    head->next->next = new ListNode(2);
    ListNode* newHead = deleteDuplicates(head);
    ListNode* curr = newHead;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

Line Notes

ListNode* current = head;Start pointer at head node

while (current && current->next)Loop until end of list

if (current->val == current->next->val)Check if current and next node are duplicates

current->next = current->next->next;Skip duplicate node

elseIf no duplicate, move pointer forward

current = current->next;Advance pointer

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function deleteDuplicates(head) {
    let current = head;
    while (current !== null && current.next !== null) {
        if (current.val === current.next.val) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
    return head;
}

// Test
const head = new ListNode(1, new ListNode(1, new ListNode(2)));
const newHead = deleteDuplicates(head);
let curr = newHead;
let output = '';
while (curr !== null) {
    output += curr.val + ' ';
    curr = curr.next;
}
console.log(output.trim());

Line Notes

let current = head;Initialize traversal pointer

while (current !== null && current.next !== null)Traverse list until last node

if (current.val === current.next.val)Check for duplicates

current.next = current.next.next;Remove duplicate node by skipping

elseIf no duplicate, move pointer forward

current = current.next;Advance pointer

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass through the list with constant extra space.

💡 For n=100, this means about 100 operations, very efficient for large inputs.

Interview Verdict: Accepted

This is the preferred approach in interviews due to clarity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 The iterative single pass approach is best for interviews due to simplicity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Nested Loops)	O(n)	O(1)	No	N/A	Mention only - shows understanding but not optimal
2. Recursive Approach	O(n)	O(n) due to recursion stack	Yes (deep recursion)	N/A	Good to mention as alternative, but iterative preferred
3. Iterative Single Pass (Optimal)	O(n)	O(1)	No	N/A	Code this approach in 95% of interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach, followed by optimized solutions. Practice coding and testing edge cases.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Describe the brute force approach and its inefficiencies.Step 3: Present the recursive approach as an alternative.Step 4: Explain the optimal iterative single pass solution.Step 5: Code the optimal solution and test with examples.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of linked list traversal, pointer manipulation, and ability to optimize from brute force to efficient in-place solutions.

Common Follow-ups

• What if the list is not sorted? → You would need a different approach, possibly using a hash set.
• Can you remove duplicates without extra space if the list is unsorted? → No, you need extra space or sorting.

💡 These follow-ups test your ability to adapt the solution to variations and understand space-time tradeoffs.

🔍

Pattern Recognition

When to Use

1) Input is a linked list, 2) List is sorted, 3) Need to remove duplicates, 4) In-place modification required

Signature Phrases

remove duplicatessorted linked listin-place modification

NOT This Pattern When

Removing duplicates from unsorted lists or arrays is a different pattern involving hashing or sorting.

Similar Problems

Remove Duplicates from Sorted List II - handles duplicates differentlyMerge Two Sorted Lists - also uses pointer manipulationIntersection of Two Linked Lists - pointer tricks for linked lists

Practice

1. You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. You need to add the two numbers and return the sum as a linked list. Which approach guarantees an optimal solution with O(max(m, n)) time and O(1) extra space?

easy

A. Use a recursive approach that creates a new list for the sum, handling carry via recursion.

B. Iteratively traverse both lists simultaneously, modifying one list in-place to store the sum and carry.

C. Convert both linked lists to integers, add them, then convert the sum back to a linked list.

D. Use a brute force approach that creates a new list node for each digit sum, ignoring in-place modification.

Solution

1. Step 1: Understand the problem constraints

   The problem requires adding two numbers represented as linked lists in reverse order, aiming for optimal time and space.

2. Step 2: Identify the approach that modifies input in-place

   Iterative traversal with in-place modification reuses existing nodes, achieving O(max(m, n)) time and O(1) extra space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   In-place iterative approach avoids extra space and handles carry efficiently [OK]

Hint: In-place iterative approach saves space and time [OK]

Common Mistakes:

• Assuming recursion is always optimal
• Ignoring space complexity by creating new nodes
• Converting lists to integers causes overflow

2. You are given a singly linked list with unsorted integer values. You need to sort the list in ascending order with O(n log n) time complexity and O(1) auxiliary space. Which algorithmic approach best fits this requirement?

easy

A. Perform a bottom-up iterative merge sort directly on the linked list without extra arrays.

B. Use a recursive quicksort on the linked list by partitioning around a pivot node.

C. Extract all values into an array, sort the array using quicksort, then rebuild the linked list.

D. Apply a greedy insertion sort by inserting nodes into a new sorted list one by one.

Solution

1. Step 1: Understand time and space constraints

   The problem requires O(n log n) time and O(1) auxiliary space, which rules out array extraction and recursive approaches that use extra space.

2. Step 2: Identify algorithm matching constraints

   Bottom-up iterative merge sort on linked lists achieves O(n log n) time and O(1) space by merging sublists iteratively without recursion or extra arrays.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bottom-up merge sort is the standard in-place linked list sorting method [OK]

Hint: Bottom-up merge sort is in-place and O(n log n) [OK]

Common Mistakes:

• Thinking quicksort is efficient on linked lists due to lack of random access
• Assuming insertion sort is efficient for large lists
• Believing array extraction is O(1) space

3. What is the space complexity of the recursive approach to remove duplicates from a sorted linked list, and why might a common alternative answer be incorrect?

medium

A. O(1) because no extra data structures are used.

B. O(n) because a hash set is used to track duplicates.

C. O(log n) because the recursion depth is halved each call.

D. O(n) due to recursion stack space in the worst case.

Solution

1. Step 1: Identify recursion depth

   In the worst case, recursion proceeds one node at a time, leading to O(n) recursive calls on the stack.

2. Step 2: Analyze space usage

   No auxiliary data structures like hash sets are used, so extra space is only recursion stack space, which is O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Recursive calls stack up to list length [OK]

Hint: Recursion stack space counts as extra space [OK]

Common Mistakes:

• Assuming O(1) space since no explicit data structures
• Confusing recursion depth with log n
• Thinking hash sets are used

4. 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

5. Consider the following buggy code for swapping nodes in pairs in a linked list:

def swapPairs(head: ListNode) -> ListNode:
    def helper(node):
        if not node or not node.next:
            return node
        first = node
        second = node.next
        # Bug: missing update of first.next to recursive call
        second.next = first
        return second
    return helper(head)

What is the root cause of the bug?

medium

A. Returning second instead of first breaks the swapped pair order.

B. Assigning second.next before first.next causes pointer cycles.

C. Missing base case for empty list causes infinite recursion.

D. Not updating first.next to point to the result of recursive call causes lost nodes.

Solution

1. Step 1: Identify pointer updates in recursion

   The correct approach sets first.next = helper(second.next) to link swapped pairs recursively.

2. Step 2: Analyze missing update

   Without updating first.next, the rest of the list is disconnected, causing lost nodes after the first swapped pair.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing first.next update breaks list continuity [OK]

Hint: Always update first.next to recursive call result [OK]

Common Mistakes:

• Forgetting to link swapped pairs recursively
• Returning wrong node as new head