Remove Duplicates from Sorted List II

🎯

Remove Duplicates from Sorted List II

mediumLINKED_LISTAmazonFacebook

Imagine cleaning up a sorted contact list where duplicate entries must be completely removed, not just reduced to one.

💡 This problem requires careful pointer manipulation in a linked list to remove all nodes that have duplicates. Beginners often struggle because they must skip entire runs of duplicates, not just remove one node, and handle edge cases like duplicates at the start or end of the list.

📋

Problem Statement

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.

The number of nodes in the list is in the range [0, 10^5].The list is sorted in ascending order.Node values are integers within the 32-bit signed integer range.

💡

Example

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

Output[1,2,5]

Nodes with values 3 and 4 appear more than once and are completely removed.

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

Output[2,3]

All nodes with value 1 are removed since they are duplicates.

• Empty list → returns empty list
• All nodes are duplicates → returns empty list
• Duplicates at the start → correctly removes initial nodes
• Duplicates at the end → correctly removes trailing nodes

⚠️

Common Mistakes

Not using a dummy head

Fails to remove duplicates at the head, causing incorrect output

✅ Always use a dummy node pointing to head to simplify edge cases

Only removing one duplicate node instead of all duplicates

Leaves some duplicate nodes in the list, violating problem requirements

✅ Skip entire runs of duplicates by moving current pointer until value changes

Moving prev pointer incorrectly when duplicates are found

Links list incorrectly, causing lost nodes or cycles

✅ Only move prev when current node is unique; otherwise, keep prev fixed while skipping duplicates

Not checking for null before accessing current.next

Runtime null pointer exceptions

✅ Always check current and current.next are not null before accessing their values

🧠

Brute Force (Nested Loops to Identify and Remove Duplicates)

💡 Starting with brute force helps understand the problem deeply by explicitly checking each node and removing duplicates step-by-step, even if inefficient.

Intuition

Traverse the list and for each node, check if it has duplicates by scanning ahead. If duplicates are found, remove all nodes with that value.

Algorithm

1. Initialize a dummy node pointing to head to handle edge cases.
2. Use two pointers: prev (initially dummy) and current (initially head).
3. For each current node, check if next nodes have the same value.
4. If duplicates found, skip all nodes with that value by adjusting prev.next.
5. Otherwise, move prev to current.
6. Move current forward until end of list.

💡 The main challenge is detecting and skipping entire runs of duplicates, not just one node, which requires nested scanning.

</>

Code

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

def deleteDuplicates(head):
    dummy = ListNode(0, head)
    prev = dummy
    current = head
    while current:
        # Check if current is start of duplicates
        if current.next and current.val == current.next.val:
            # Skip all nodes with current.val
            val_to_remove = current.val
            while current and current.val == val_to_remove:
                current = current.next
            prev.next = current
        else:
            prev = current
            current = current.next
    return dummy.next

# Driver code to test
if __name__ == '__main__':
    # Helper to create list
    def create_list(arr):
        dummy = ListNode(0)
        cur = dummy
        for v in arr:
            cur.next = ListNode(v)
            cur = cur.next
        return dummy.next

    # Helper to print list
    def print_list(node):
        vals = []
        while node:
            vals.append(str(node.val))
            node = node.next
        print('[' + ','.join(vals) + ']')

    head = create_list([1,2,3,3,4,4,5])
    res = deleteDuplicates(head)
    print_list(res)  # Expected: [1,2,5]

Line Notes

dummy = ListNode(0, head)Create dummy to simplify edge cases like duplicates at head

prev = dummyPrev tracks last node before current run, needed to reconnect list

while current:Traverse entire list until no nodes left

if current.next and current.val == current.next.val:Detect start of duplicates by comparing current and next values

while current and current.val == val_to_remove:Skip all nodes with duplicate value

prev.next = currentLink prev to first non-duplicate node after duplicates

else:If no duplicates, move prev forward

return dummy.nextReturn head of modified list, skipping dummy

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

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode current = head;
        while (current != null) {
            if (current.next != null && current.val == current.next.val) {
                int valToRemove = current.val;
                while (current != null && current.val == valToRemove) {
                    current = current.next;
                }
                prev.next = current;
            } else {
                prev = current;
                current = current.next;
            }
        }
        return dummy.next;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode head = createList(new int[]{1,2,3,3,4,4,5});
        ListNode res = sol.deleteDuplicates(head);
        printList(res); // Expected: [1,2,5]
    }

    static ListNode createList(int[] arr) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        for (int v : arr) {
            cur.next = new ListNode(v);
            cur = cur.next;
        }
        return dummy.next;
    }

    static void printList(ListNode node) {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        while (node != null) {
            sb.append(node.val);
            if (node.next != null) sb.append(",");
            node = node.next;
        }
        sb.append("]");
        System.out.println(sb.toString());
    }
}

Line Notes

ListNode dummy = new ListNode(0);Dummy node to handle edge cases uniformly

ListNode prev = dummy;Prev pointer to reconnect list after removing duplicates

while (current != null)Traverse all nodes in the list

if (current.next != null && current.val == current.next.val)Detect duplicate sequence start

while (current != null && current.val == valToRemove)Skip all nodes with duplicate value

prev.next = current;Link prev to node after duplicates

else { prev = current; current = current.next; }Move pointers forward if no duplicates

return dummy.next;Return new head skipping dummy

#include <iostream>
using namespace std;

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

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* prev = &dummy;
        ListNode* current = head;
        while (current) {
            if (current->next && current->val == current->next->val) {
                int valToRemove = current->val;
                while (current && current->val == valToRemove) {
                    current = current->next;
                }
                prev->next = current;
            } else {
                prev = current;
                current = current->next;
            }
        }
        return dummy.next;
    }
};

// Helper functions
ListNode* createList(int arr[], int n) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    for (int i = 0; i < n; i++) {
        cur->next = new ListNode(arr[i]);
        cur = cur->next;
    }
    return dummy.next;
}

void printList(ListNode* head) {
    cout << "[";
    while (head) {
        cout << head->val;
        if (head->next) cout << ",";
        head = head->next;
    }
    cout << "]" << endl;
}

int main() {
    int arr[] = {1,2,3,3,4,4,5};
    ListNode* head = createList(arr, 7);
    Solution sol;
    ListNode* res = sol.deleteDuplicates(head);
    printList(res); // Expected: [1,2,5]
    return 0;
}

Line Notes

ListNode dummy(0);Dummy node simplifies edge case handling

ListNode* prev = &dummy;Prev pointer to reconnect after duplicates

while (current) {Traverse entire list

if (current->next && current->val == current->next->val) {Detect duplicate sequence start

while (current && current->val == valToRemove) {Skip all duplicates

prev->next = current;Link prev to node after duplicates

else { prev = current; current = current->next; }Move pointers forward if no duplicates

return dummy.next;Return new head skipping dummy

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function deleteDuplicates(head) {
    let dummy = new ListNode(0, head);
    let prev = dummy;
    let current = head;
    while (current) {
        if (current.next && current.val === current.next.val) {
            let valToRemove = current.val;
            while (current && current.val === valToRemove) {
                current = current.next;
            }
            prev.next = current;
        } else {
            prev = current;
            current = current.next;
        }
    }
    return dummy.next;
}

// Helper to create list
function createList(arr) {
    let dummy = new ListNode(0);
    let cur = dummy;
    for (let v of arr) {
        cur.next = new ListNode(v);
        cur = cur.next;
    }
    return dummy.next;
}

// Helper to print list
function printList(head) {
    let vals = [];
    while (head) {
        vals.push(head.val);
        head = head.next;
    }
    console.log('[' + vals.join(',') + ']');
}

// Test
let head = createList([1,2,3,3,4,4,5]);
let res = deleteDuplicates(head);
printList(res); // Expected: [1,2,5]

Line Notes

let dummy = new ListNode(0, head);Dummy node to handle edge cases uniformly

let prev = dummy;Prev pointer to reconnect list after duplicates

while (current) {Traverse all nodes

if (current.next && current.val === current.next.val) {Detect start of duplicates

while (current && current.val === valToRemove) {Skip all duplicates

prev.next = current;Link prev to node after duplicates

else { prev = current; current = current.next; }Move pointers forward if no duplicates

return dummy.next;Return new head skipping dummy

⏱

Complexity

TimeO(n)

SpaceO(1)

Traverse the list once, skipping duplicates in a single pass without nested loops.

💡 For n=20, this means about 20 operations, which is efficient for large inputs.

Interview Verdict: Accepted / Optimal iterative solution

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

🧠

Improved Iterative with Single Pass and Dummy Head

💡 This approach improves efficiency by using a single pass with careful pointer updates to skip duplicates immediately.

Intuition

Since the list is sorted, duplicates appear consecutively. We can skip entire duplicate runs by comparing current and next nodes and adjusting pointers accordingly.

Algorithm

1. Create a dummy node pointing to head to handle edge cases.
2. Initialize prev pointer to dummy and current pointer to head.
3. While current is not null, check if current has duplicates by comparing with next node.
4. If duplicates exist, skip all nodes with that value by moving current forward.
5. Link prev.next to current after skipping duplicates.
6. If no duplicates, move prev to current.
7. Move current forward until end of list.

💡 The key is to detect duplicates early and skip them entirely in one pass without nested loops.

</>

Code

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

def deleteDuplicates(head):
    dummy = ListNode(0, head)
    prev = dummy
    current = head
    while current:
        if current.next and current.val == current.next.val:
            val_to_remove = current.val
            while current and current.val == val_to_remove:
                current = current.next
            prev.next = current
        else:
            prev = current
            current = current.next
    return dummy.next

# Driver code
if __name__ == '__main__':
    def create_list(arr):
        dummy = ListNode(0)
        cur = dummy
        for v in arr:
            cur.next = ListNode(v)
            cur = cur.next
        return dummy.next

    def print_list(node):
        vals = []
        while node:
            vals.append(str(node.val))
            node = node.next
        print('[' + ','.join(vals) + ']')

    head = create_list([1,1,2,3,3])
    res = deleteDuplicates(head)
    print_list(res)  # Expected: [2]

Line Notes

dummy = ListNode(0, head)Dummy node simplifies handling head duplicates

prev = dummyPrev tracks last confirmed unique node

while current:Traverse entire list once

if current.next and current.val == current.next.val:Detect start of duplicates

while current and current.val == val_to_remove:Skip all duplicates in one go

prev.next = currentLink prev to first unique node after duplicates

else: prev = currentMove prev forward if current is unique

return dummy.nextReturn new head skipping dummy

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

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode current = head;
        while (current != null) {
            if (current.next != null && current.val == current.next.val) {
                int valToRemove = current.val;
                while (current != null && current.val == valToRemove) {
                    current = current.next;
                }
                prev.next = current;
            } else {
                prev = current;
                current = current.next;
            }
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode head = createList(new int[]{1,1,2,3,3});
        ListNode res = sol.deleteDuplicates(head);
        printList(res); // Expected: [2]
    }

    static ListNode createList(int[] arr) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        for (int v : arr) {
            cur.next = new ListNode(v);
            cur = cur.next;
        }
        return dummy.next;
    }

    static void printList(ListNode node) {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        while (node != null) {
            sb.append(node.val);
            if (node.next != null) sb.append(",");
            node = node.next;
        }
        sb.append("]");
        System.out.println(sb.toString());
    }
}

Line Notes

ListNode dummy = new ListNode(0);Dummy node to handle edge cases

ListNode prev = dummy;Prev pointer to reconnect after duplicates

while (current != null)Traverse list once

if (current.next != null && current.val == current.next.val)Detect duplicates start

while (current != null && current.val == valToRemove)Skip all duplicates

prev.next = current;Link prev to node after duplicates

else { prev = current; current = current.next; }Move pointers forward if unique

return dummy.next;Return new head skipping dummy

#include <iostream>
using namespace std;

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

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* prev = &dummy;
        ListNode* current = head;
        while (current) {
            if (current->next && current->val == current->next->val) {
                int valToRemove = current->val;
                while (current && current->val == valToRemove) {
                    current = current->next;
                }
                prev->next = current;
            } else {
                prev = current;
                current = current->next;
            }
        }
        return dummy.next;
    }
};

ListNode* createList(int arr[], int n) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    for (int i = 0; i < n; i++) {
        cur->next = new ListNode(arr[i]);
        cur = cur->next;
    }
    return dummy.next;
}

void printList(ListNode* head) {
    cout << "[";
    while (head) {
        cout << head->val;
        if (head->next) cout << ",";
        head = head->next;
    }
    cout << "]" << endl;
}

int main() {
    int arr[] = {1,1,2,3,3};
    ListNode* head = createList(arr, 5);
    Solution sol;
    ListNode* res = sol.deleteDuplicates(head);
    printList(res); // Expected: [2]
    return 0;
}

Line Notes

ListNode dummy(0);Dummy node simplifies edge case handling

ListNode* prev = &dummy;Prev pointer to reconnect list

while (current) {Traverse list once

if (current->next && current->val == current->next->val) {Detect duplicates start

while (current && current->val == valToRemove) {Skip all duplicates

prev->next = current;Link prev to node after duplicates

else { prev = current; current = current->next; }Move pointers forward if unique

return dummy.next;Return new head skipping dummy

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function deleteDuplicates(head) {
    let dummy = new ListNode(0, head);
    let prev = dummy;
    let current = head;
    while (current) {
        if (current.next && current.val === current.next.val) {
            let valToRemove = current.val;
            while (current && current.val === valToRemove) {
                current = current.next;
            }
            prev.next = current;
        } else {
            prev = current;
            current = current.next;
        }
    }
    return dummy.next;
}

function createList(arr) {
    let dummy = new ListNode(0);
    let cur = dummy;
    for (let v of arr) {
        cur.next = new ListNode(v);
        cur = cur.next;
    }
    return dummy.next;
}

function printList(head) {
    let vals = [];
    while (head) {
        vals.push(head.val);
        head = head.next;
    }
    console.log('[' + vals.join(',') + ']');
}

let head = createList([1,1,2,3,3]);
let res = deleteDuplicates(head);
printList(res); // Expected: [2]

Line Notes

let dummy = new ListNode(0, head);Dummy node to handle edge cases

let prev = dummy;Prev pointer to reconnect list

while (current) {Traverse list once

if (current.next && current.val === current.next.val) {Detect duplicates start

while (current && current.val === valToRemove) {Skip all duplicates

prev.next = current;Link prev to node after duplicates

else { prev = current; current = current.next; }Move pointers forward if unique

return dummy.next;Return new head skipping dummy

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass through the list with constant extra space.

💡 For n=20, this means about 20 operations, which is efficient for large inputs.

Interview Verdict: Accepted / Optimal iterative solution

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

🧠

Recursive Approach

💡 Recursion provides a clean and elegant way to solve the problem by processing the list from head to tail, but requires understanding of recursion and stack.

Intuition

If the head has duplicates, skip all nodes with that value and recurse on the rest. Otherwise, keep head and recurse on head.next.

Algorithm

1. If head is null or only one node, return head.
2. If head has duplicates (head.val == head.next.val), skip all nodes with that value.
3. Recurse on the node after duplicates and return the result.
4. If no duplicates at head, set head.next to recursion result on head.next and return head.

💡 The challenge is correctly skipping duplicates and linking the recursive results.

</>

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
    if head.val == head.next.val:
        val_to_remove = head.val
        while head and head.val == val_to_remove:
            head = head.next
        return deleteDuplicates(head)
    else:
        head.next = deleteDuplicates(head.next)
        return head

# Driver code
if __name__ == '__main__':
    def create_list(arr):
        dummy = ListNode(0)
        cur = dummy
        for v in arr:
            cur.next = ListNode(v)
            cur = cur.next
        return dummy.next

    def print_list(node):
        vals = []
        while node:
            vals.append(str(node.val))
            node = node.next
        print('[' + ','.join(vals) + ']')

    head = create_list([1,2,3,3,4,4,5])
    res = deleteDuplicates(head)
    print_list(res)  # Expected: [1,2,5]

Line Notes

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

if head.val == head.next.val:Detect duplicates at head

while head and head.val == val_to_remove:Skip all duplicates

return deleteDuplicates(head)Recurse on remaining list after duplicates

head.next = deleteDuplicates(head.next)Recurse on next node if head unique

return headReturn current unique node

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

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode head = createList(new int[]{1,2,3,3,4,4,5});
        ListNode res = sol.deleteDuplicates(head);
        printList(res); // Expected: [1,2,5]
    }

    static ListNode createList(int[] arr) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        for (int v : arr) {
            cur.next = new ListNode(v);
            cur = cur.next;
        }
        return dummy.next;
    }

    static void printList(ListNode node) {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        while (node != null) {
            sb.append(node.val);
            if (node.next != null) sb.append(",");
            node = node.next;
        }
        sb.append("]");
        System.out.println(sb.toString());
    }
}

Line Notes

if (head == null || head.next == null) return head;Base case: empty or single node list

if (head.val == head.next.val)Detect duplicates at head

while (head != null && head.val == valToRemove)Skip all duplicates

return deleteDuplicates(head);Recurse on remaining list

head.next = deleteDuplicates(head.next);Recurse on next node if unique

return head;Return current unique node

#include <iostream>
using namespace std;

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

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head || !head->next) return head;
        if (head->val == head->next->val) {
            int valToRemove = head->val;
            while (head && head->val == valToRemove) {
                head = head->next;
            }
            return deleteDuplicates(head);
        } else {
            head->next = deleteDuplicates(head->next);
            return head;
        }
    }
};

ListNode* createList(int arr[], int n) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    for (int i = 0; i < n; i++) {
        cur->next = new ListNode(arr[i]);
        cur = cur->next;
    }
    return dummy.next;
}

void printList(ListNode* head) {
    cout << "[";
    while (head) {
        cout << head->val;
        if (head->next) cout << ",";
        head = head->next;
    }
    cout << "]" << endl;
}

int main() {
    int arr[] = {1,2,3,3,4,4,5};
    ListNode* head = createList(arr, 7);
    Solution sol;
    ListNode* res = sol.deleteDuplicates(head);
    printList(res); // Expected: [1,2,5]
    return 0;
}

Line Notes

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

if (head->val == head->next->val)Detect duplicates at head

while (head && head->val == valToRemove)Skip all duplicates

return deleteDuplicates(head);Recurse on remaining list

head->next = deleteDuplicates(head->next);Recurse on next node if unique

return head;Return current unique node

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

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

function createList(arr) {
    let dummy = new ListNode(0);
    let cur = dummy;
    for (let v of arr) {
        cur.next = new ListNode(v);
        cur = cur.next;
    }
    return dummy.next;
}

function printList(head) {
    let vals = [];
    while (head) {
        vals.push(head.val);
        head = head.next;
    }
    console.log('[' + vals.join(',') + ']');
}

let head = createList([1,2,3,3,4,4,5]);
let res = deleteDuplicates(head);
printList(res); // Expected: [1,2,5]

Line Notes

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

if (head.val === head.next.val)Detect duplicates at head

while (head && head.val === valToRemove)Skip all duplicates

return deleteDuplicates(head);Recurse on remaining list

head.next = deleteDuplicates(head.next);Recurse on next node if unique

return head;Return current unique node

⏱

Complexity

TimeO(n)

SpaceO(n) due to recursion stack

Each node is visited once, but recursion adds stack space proportional to list length.

💡 For n=20, recursion depth is 20, which may cause stack overflow in some languages.

Interview Verdict: Accepted / Elegant but uses extra stack space

Recursion is clean but may not be preferred in interviews due to stack overhead.

📊

All Approaches - One-Glance Tradeoffs

💡 The optimal iterative approach with dummy head is recommended for 95% of interviews due to its clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Optimal Iterative	O(n)	O(1)	No	N/A	Code this approach in interviews
3. Recursive	O(n)	O(n) due to recursion stack	Yes for large n	N/A	Mention as elegant alternative; code if comfortable with recursion

💼

Interview Strategy

💡 Use this guide to understand the problem deeply and practice all approaches before your interview. Focus on pointer manipulation and edge cases.

How to Present

Clarify problem requirements and confirm input is sorted.Explain brute force approach to show understanding of duplicates removal.Present optimal iterative approach with dummy head and pointer skipping.Optionally mention recursive approach for elegance.Write clean code and test edge cases.

Time Allocation

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

What the Interviewer Tests

Interviewer tests your ability to manipulate pointers correctly, handle edge cases, and optimize from brute force to efficient solution.

Common Follow-ups

• What if the list is not sorted? → Need extra data structure like a hash set.
• Can you do it without a dummy node? → Yes, but code is more complex and error-prone.

💡 These follow-ups test your adaptability and deeper understanding of linked list manipulations.

🔍

Pattern Recognition

When to Use

1) Input is a sorted linked list, 2) Need to remove all duplicates completely, 3) Must do in-place with pointer manipulation, 4) Output list must remain sorted.

Signature Phrases

'delete all nodes that have duplicate numbers''leaving only distinct numbers from the original list'

NOT This Pattern When

Removing duplicates but keeping one copy (like Remove Duplicates from Sorted List I) is a different pattern.

Similar Problems

Remove Duplicates from Sorted List I - keeps one copy of duplicatesDelete Node in a Linked List - pointer manipulation practiceRemove Linked List Elements - removing nodes by value

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 k sorted linked lists and need to merge them into one sorted linked list efficiently. Which approach guarantees the optimal time complexity for this problem?

easy

A. Merge all lists into one array, then sort the array and rebuild the linked list.

B. Use dynamic programming to store intermediate merged results and avoid repeated merges.

C. Use a min-heap (priority queue) to repeatedly extract the smallest node among the heads of the lists.

D. Merge the lists one by one sequentially, merging two lists at a time from left to right.

Solution

1. Step 1: Understand problem constraints

   We have k sorted linked lists and want to merge them efficiently.

2. Step 2: Compare approaches

   Brute force sorting all nodes is O(N log N). Sequential merges cost O(kN). Min-heap approach extracts smallest node in O(log k) time, total O(N log k), which is optimal.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Min-heap approach uses priority queue to achieve O(N log k) [OK]

Hint: Min-heap merges k lists in O(N log k) time [OK]

Common Mistakes:

• Thinking sequential merges are optimal
• Assuming sorting all nodes is best
• Confusing DP with merge approach

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

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

5. Suppose the problem is modified so that the linked list is circular (the last node points back to the head). Which of the following modifications to the recursive swapPairs function correctly handles swapping nodes in pairs without causing infinite recursion or losing nodes?

hard

A. Modify the base case to stop recursion when the next node is the head, breaking the cycle.

B. Add a visited set to track nodes and stop recursion when a node repeats.

C. Use the same recursive approach without changes; it naturally terminates on circular lists.

D. Convert the circular list to a linear list by breaking the cycle before swapping.

Solution

1. Step 1: Understand circular list implications

   In a circular list, naive recursion never reaches a null node, causing infinite recursion.

2. Step 2: Modify base case to detect cycle

   Stopping recursion when next node is the head prevents infinite loops and preserves all nodes.

3. Step 3: Compare alternatives

   Using a visited set adds overhead; breaking cycle beforehand changes problem constraints; naive recursion fails.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Base case adjusted for cycle detection prevents infinite recursion [OK]

Hint: Detect cycle in base case to stop recursion [OK]

Common Mistakes:

• Ignoring cycle causes infinite recursion
• Trying naive recursion without cycle check