Remove Duplicates from Sorted List II

Problem Statement

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers. Return the head of the modified linked list.

What to notice first

• The list is sorted, which means all duplicate values are consecutive.
• You must delete entire groups of duplicates, not just reduce them to one — if a value appears 2+ times, it’s gone entirely.
• A dummy node is crucial: if the head itself is part of a duplicate group, the dummy becomes the new head.
• Single-pass approach tracks “prev” (last non-duplicate node) and checks if the current and next nodes match.

Examples

Input	Output	Explanation
1 → 2 → 3 → 3 → 4 → 4 → 5	1 → 2 → 5	Remove all 3s and 4s (appeared 2+ times)
1 → 1 → 1 → 2 → 3	2 → 3	Remove all 1s
1 → 1	(empty)	Both nodes are duplicates; return empty list

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.

Real-World Applications

Where this pattern appears

• Log deduplication — remove entries that appear multiple times in a sorted log file.
• Database cleanup — strip out duplicate transaction records that violate uniqueness constraints.
• Version control — remove commits that share the same message hash from a history.
• Signal processing — filter out duplicate measurements in a time-series stream.

Complexity Comparison

Approach	Time	Space	Best When
Hash Set	O(n)	O(n)	First-pass understanding; counting duplicates is intuitive
Single Pass	O(n)	O(1)	Memory is limited; elegant pointer manipulation

Which approach should you learn first?

• Learn Single Pass first — it demonstrates linked-list traversal and handles the dummy-node pattern.
• Use Hash Set as a reference: it is easier to visualize and debug, but uses extra space.

Optimal & Elegant

Single Pass

O(n) time · O(1) space

Easy to Understand

Hash Set

O(n) time · O(n) space

Approach 1: Single Pass (Two Pointers)

★ Recommended

Use a dummy node and a prev pointer. Iterate through the list; when you find a duplicate (current and next have the same value), skip all nodes with that value. Otherwise, advance prev and move to the next node.

⏱ Time O(n) One pass through list 💾 Space O(1) Only pointer variables

Step-by-step Example

Input: 1 → 2 → 3 → 3 → 4 → 4 → 5

Step	Prev	Current	Action	Note
1	dummy	1	1 ≠ 2 → advance prev	1 is unique
2	1	2	2 ≠ 3 → advance prev	2 is unique
3	2	3	3 = 3 → skip all 3s	Duplicate detected
4	2	4	4 = 4 → skip all 4s	Duplicate detected
5	2	5	No next → done	5 is unique
Result			dummy → 1 → 2 → 5	Duplicates removed

Animated walkthrough

How pointers identify and remove duplicate nodes

Watch as prev marks the last valid node, and current skips all duplicates when consecutive nodes match.

Back Autoplay Next Reset

Step 1 of 8

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function deleteDuplicates(head):
    dummy = new ListNode(0)
    dummy.next = head
    prev = dummy
    current = head

    while current != null:
        if current.next != null and current.val == current.next.val:
            // Skip all duplicates
            value = current.val
            while current != null and current.val == value:
                current = current.next
            // Link prev to the first non-duplicate node
            prev.next = current
        else:
            // Unique node, keep it
            prev = prev.next
            current = current.next

    return dummy.next

Solution Code

Python

remove_duplicates_from_sorted_list_ii_single_pass.py

from typing import Optional


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


def deleteDuplicates(head: Optional[ListNode]) -> Optional[ListNode]:
    """
    Remove all nodes with duplicate values from sorted linked list in single pass.

    Approach: Use a dummy node and prev pointer. When we find duplicates, skip all nodes
    with that value by advancing current and updating prev.next to point past the group.
    Time: O(n) — single pass through the list
    Space: O(1) — only pointer variables
    """
    if not head:
        return None

    # Create dummy node to handle edge case where head is duplicate
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy
    current = head

    while current:
        # Check if current node is the start of a duplicate group
        if current.next and current.val == current.next.val:
            # Skip all nodes with the same value
            value = current.val
            while current and current.val == value:
                current = current.next
            # Link prev to the first non-duplicate node
            prev.next = current
        else:
            # Current node is unique, keep it
            prev = current
            current = current.next

    return dummy.next


# Test cases
if __name__ == "__main__":
    # Helper function to create linked list from array
    def create_list(arr):
        if not arr:
            return None
        head = ListNode(arr[0])
        current = head
        for val in arr[1:]:
            current.next = ListNode(val)
            current = current.next
        return head

    # Helper function to convert linked list to array
    def list_to_array(head):
        result = []
        current = head
        while current:
            result.append(current.val)
            current = current.next
        return result

    # Test case 1: [1,2,3,3,4,4,5]
    head1 = create_list([1, 2, 3, 3, 4, 4, 5])
    result1 = deleteDuplicates(head1)
    print(list_to_array(result1))  # [1, 2, 5]

    # Test case 2: [1,1,1,2,3]
    head2 = create_list([1, 1, 1, 2, 3])
    result2 = deleteDuplicates(head2)
    print(list_to_array(result2))  # [2, 3]

    # Test case 3: [1,1]
    head3 = create_list([1, 1])
    result3 = deleteDuplicates(head3)
    print(list_to_array(result3))  # []

C++

remove_duplicates_from_sorted_list_ii_single_pass.cpp

#include <iostream>
#include <vector>
using namespace std;

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

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        /**
         * Remove all nodes with duplicate values from sorted linked list in single pass.
         *
         * Approach: Use a dummy node and prev pointer. When we find duplicates, skip all
         * nodes with that value by advancing current and updating prev->next.
         * Time: O(n) — single pass through the list
         * Space: O(1) — only pointer variables
         */
        if (!head) return nullptr;

        // Create dummy node to handle edge case where head is duplicate
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* prev = dummy;
        ListNode* current = head;

        while (current) {
            // Check if current node is the start of a duplicate group
            if (current->next && current->val == current->next->val) {
                // Skip all nodes with the same value
                int value = current->val;
                while (current && current->val == value) {
                    current = current->next;
                }
                // Link prev to the first non-duplicate node
                prev->next = current;
            } else {
                // Current node is unique, keep it
                prev = current;
                current = current->next;
            }
        }

        ListNode* result = dummy->next;
        delete dummy;
        return result;
    }
};

// Test cases
void printList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "null\n";
}

ListNode* createList(vector<int> arr) {
    if (arr.empty()) return nullptr;
    ListNode* head = new ListNode(arr[0]);
    ListNode* current = head;
    for (size_t i = 1; i < arr.size(); i++) {
        current->next = new ListNode(arr[i]);
        current = current->next;
    }
    return head;
}

int main() {
    Solution sol;

    // Test case 1: [1,2,3,3,4,4,5]
    ListNode* head1 = createList({1, 2, 3, 3, 4, 4, 5});
    cout << "Test 1: ";
    printList(sol.deleteDuplicates(head1));  // 1 -> 2 -> 5 -> null

    // Test case 2: [1,1,1,2,3]
    ListNode* head2 = createList({1, 1, 1, 2, 3});
    cout << "Test 2: ";
    printList(sol.deleteDuplicates(head2));  // 2 -> 3 -> null

    // Test case 3: [1,1]
    ListNode* head3 = createList({1, 1});
    cout << "Test 3: ";
    printList(sol.deleteDuplicates(head3));  // null

    return 0;
}

Java

remove_duplicates_from_sorted_list_ii_single_pass.java

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

class Solution {
    /**
     * Remove all nodes with duplicate values from sorted linked list in single pass.
     *
     * Approach: Use a dummy node and prev pointer. When we find duplicates, skip all
     * nodes with that value by advancing current and updating prev.next.
     * Time: O(n) — single pass through the list
     * Space: O(1) — only pointer variables
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;

        // Create dummy node to handle edge case where head is duplicate
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode current = head;

        while (current != null) {
            // Check if current node is the start of a duplicate group
            if (current.next != null && current.val == current.next.val) {
                // Skip all nodes with the same value
                int value = current.val;
                while (current != null && current.val == value) {
                    current = current.next;
                }
                // Link prev to the first non-duplicate node
                prev.next = current;
            } else {
                // Current node is unique, keep it
                prev = current;
                current = current.next;
            }
        }

        return dummy.next;
    }

    // Helper function to create linked list from array
    public static ListNode createList(int[] arr) {
        if (arr.length == 0) return null;
        ListNode head = new ListNode(arr[0]);
        ListNode current = head;
        for (int i = 1; i < arr.length; i++) {
            current.next = new ListNode(arr[i]);
            current = current.next;
        }
        return head;
    }

    // Helper function to print linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        // Test case 1: [1,2,3,3,4,4,5]
        ListNode head1 = createList(new int[]{1, 2, 3, 3, 4, 4, 5});
        System.out.print("Test 1: ");
        printList(sol.deleteDuplicates(head1));  // 1 -> 2 -> 5 -> null

        // Test case 2: [1,1,1,2,3]
        ListNode head2 = createList(new int[]{1, 1, 1, 2, 3});
        System.out.print("Test 2: ");
        printList(sol.deleteDuplicates(head2));  // 2 -> 3 -> null

        // Test case 3: [1,1]
        ListNode head3 = createList(new int[]{1, 1});
        System.out.print("Test 3: ");
        printList(sol.deleteDuplicates(head3));  // null
    }
}

JavaScript

remove_duplicates_from_sorted_list_ii_single_pass.js

/**
 * Definition for singly-linked list node.
 */
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

/**
 * Remove all nodes with duplicate values from sorted linked list in single pass.
 *
 * Approach: Use a dummy node and prev pointer. When we find duplicates, skip all
 * nodes with that value by advancing current and updating prev.next.
 * Time: O(n) — single pass through the list
 * Space: O(1) — only pointer variables
 *
 * @param {ListNode} head
 * @return {ListNode}
 */
function deleteDuplicates(head) {
    if (!head) return null;

    // Create dummy node to handle edge case where head is duplicate
    const dummy = new ListNode(0);
    dummy.next = head;
    let prev = dummy;
    let current = head;

    while (current) {
        // Check if current node is the start of a duplicate group
        if (current.next && current.val === current.next.val) {
            // Skip all nodes with the same value
            const value = current.val;
            while (current && current.val === value) {
                current = current.next;
            }
            // Link prev to the first non-duplicate node
            prev.next = current;
        } else {
            // Current node is unique, keep it
            prev = current;
            current = current.next;
        }
    }

    return dummy.next;
}

/**
 * Helper function to create linked list from array
 */
function createList(arr) {
    if (arr.length === 0) return null;
    const head = new ListNode(arr[0]);
    let current = head;
    for (let i = 1; i < arr.length; i++) {
        current.next = new ListNode(arr[i]);
        current = current.next;
    }
    return head;
}

/**
 * Helper function to print linked list
 */
function printList(head) {
    let result = '';
    while (head) {
        result += head.val + ' -> ';
        head = head.next;
    }
    result += 'null';
    console.log(result);
}

// Test cases
console.log('Test 1:');
const head1 = createList([1, 2, 3, 3, 4, 4, 5]);
printList(deleteDuplicates(head1));  // 1 -> 2 -> 5 -> null

console.log('Test 2:');
const head2 = createList([1, 1, 1, 2, 3]);
printList(deleteDuplicates(head2));  // 2 -> 3 -> null

console.log('Test 3:');
const head3 = createList([1, 1]);
printList(deleteDuplicates(head3));  // null

module.exports = { deleteDuplicates, ListNode };

Rust

remove_duplicates_from_sorted_list_ii_single_pass.rs

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}

/**
 * Remove all nodes with duplicate values from sorted linked list in single pass.
 *
 * Approach: Use a dummy node and prev pointer. When we find duplicates, skip all
 * nodes with that value by advancing current and updating prev.next.
 * Time: O(n) — single pass through the list
 * Space: O(1) — only pointer variables
 */
pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    if head.is_none() {
        return None;
    }

    // Create dummy node to handle edge case where head is duplicate
    let mut dummy = Box::new(ListNode::new(0));
    dummy.next = head;
    let mut prev = &mut dummy;
    let mut current = prev.next.take();

    while let Some(mut node) = current {
        current = node.next.take();

        // Check if current node is the start of a duplicate group
        if let Some(next_node) = &current {
            if node.val == next_node.val {
                // Skip all nodes with the same value
                let value = node.val;
                while let Some(n) = current {
                    if n.val != value {
                        current = Some(n);
                        break;
                    }
                    current = n.next;
                }
                // Link prev to the first non-duplicate node
                prev.next = current;
                current = prev.next.take();
                continue;
            }
        }

        // Current node is unique, keep it
        prev.next = Some(node);
        prev = prev.next.as_mut().unwrap();
    }

    dummy.next.take()
}

fn main() {
    // Test case 1: [1,2,3,3,4,4,5]
    let head1 = Some(Box::new(ListNode {
        val: 1,
        next: Some(Box::new(ListNode {
            val: 2,
            next: Some(Box::new(ListNode {
                val: 3,
                next: Some(Box::new(ListNode {
                    val: 3,
                    next: Some(Box::new(ListNode {
                        val: 4,
                        next: Some(Box::new(ListNode {
                            val: 4,
                            next: Some(Box::new(ListNode {
                                val: 5,
                                next: None,
                            })),
                        })),
                    })),
                })),
            })),
        })),
    }));
    println!("Test 1: {:?}", delete_duplicates(head1));  // 1 -> 2 -> 5

    // Test case 2: [1,1,1,2,3]
    let head2 = Some(Box::new(ListNode {
        val: 1,
        next: Some(Box::new(ListNode {
            val: 1,
            next: Some(Box::new(ListNode {
                val: 1,
                next: Some(Box::new(ListNode {
                    val: 2,
                    next: Some(Box::new(ListNode {
                        val: 3,
                        next: None,
                    })),
                })),
            })),
        })),
    }));
    println!("Test 2: {:?}", delete_duplicates(head2));  // 2 -> 3

    // Test case 3: [1,1]
    let head3 = Some(Box::new(ListNode {
        val: 1,
        next: Some(Box::new(ListNode {
            val: 1,
            next: None,
        })),
    }));
    println!("Test 3: {:?}", delete_duplicates(head3));  // null
}

Go

remove_duplicates_from_sorted_list_ii_single_pass.go

package main

import "fmt"

type ListNode struct {
  Val  int
  Next *ListNode
}

/**
 * Remove all nodes with duplicate values from sorted linked list in single pass.
 *
 * Approach: Use a dummy node and prev pointer. When we find duplicates, skip all
 * nodes with that value by advancing current and updating prev.Next.
 * Time: O(n) — single pass through the list
 * Space: O(1) — only pointer variables
 */
func deleteDuplicates(head *ListNode) *ListNode {
  if head == nil {
    return nil
  }

  // Create dummy node to handle edge case where head is duplicate
  dummy := &ListNode{Val: 0}
  dummy.Next = head
  prev := dummy
  current := head

  for current != nil {
    // Check if current node is the start of a duplicate group
    if current.Next != nil && current.Val == current.Next.Val {
      // Skip all nodes with the same value
      value := current.Val
      for current != nil && current.Val == value {
        current = current.Next
      }
      // Link prev to the first non-duplicate node
      prev.Next = current
    } else {
      // Current node is unique, keep it
      prev = current
      current = current.Next
    }
  }

  return dummy.Next
}

// Helper function to create linked list from array
func createList(arr []int) *ListNode {
  if len(arr) == 0 {
    return nil
  }
  head := &ListNode{Val: arr[0]}
  current := head
  for i := 1; i < len(arr); i++ {
    current.Next = &ListNode{Val: arr[i]}
    current = current.Next
  }
  return head
}

// Helper function to print linked list
func printList(head *ListNode) {
  for head != nil {
    fmt.Printf("%d -> ", head.Val)
    head = head.Next
  }
  fmt.Println("null")
}

func main() {
  // Test case 1: [1,2,3,3,4,4,5]
  head1 := createList([]int{1, 2, 3, 3, 4, 4, 5})
  fmt.Print("Test 1: ")
  printList(deleteDuplicates(head1))  // 1 -> 2 -> 5 -> null

  // Test case 2: [1,1,1,2,3]
  head2 := createList([]int{1, 1, 1, 2, 3})
  fmt.Print("Test 2: ")
  printList(deleteDuplicates(head2))  // 2 -> 3 -> null

  // Test case 3: [1,1]
  head3 := createList([]int{1, 1})
  fmt.Print("Test 3: ")
  printList(deleteDuplicates(head3))  // null
}

Approach 2: Hash Set

✓ Simple

First pass: count the frequency of each value using a set or hash map. Second pass: build the result list, skipping any node whose value appeared more than once.

⏱ Time O(n) Two passes 💾 Space O(n) Hash set stores unique values

Step-by-step Example

Input: 1 → 2 → 3 → 3 → 4 → 4 → 5

Step	Value	Frequency	Keep?
Pass 1	1	1	Yes
	2	1	Yes
	3	2	No
	4	2	No
	5	1	Yes
Pass 2	Keep: 1 → 2 → 5

Pseudocode

function deleteDuplicates(head):
    // Count frequencies
    freq = {}
    current = head
    while current != null:
        freq[current.val] = freq.get(current.val, 0) + 1
        current = current.next

    // Build result list
    dummy = new ListNode(0)
    dummy.next = head
    prev = dummy
    current = head

    while current != null:
        if freq[current.val] == 1:
            prev = current
            current = current.next
        else:
            // Skip this node (duplicate)
            prev.next = current.next
            current = current.next

    return dummy.next

Solution Code

Python

remove_duplicates_from_sorted_list_ii_hash_set.py

from typing import Optional


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


def deleteDuplicates(head: Optional[ListNode]) -> Optional[ListNode]:
    """
    Remove all nodes with duplicate values from sorted linked list using hash set.

    Approach: Count frequency of each value, then rebuild the list with unique values only.
    Time: O(n) — two passes through the list
    Space: O(n) — hash map stores frequencies
    """
    if not head:
        return None

    # Count frequencies
    freq = {}
    current = head
    while current:
        freq[current.val] = freq.get(current.val, 0) + 1
        current = current.next

    # Build result list with unique values only
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy
    current = head

    while current:
        if freq[current.val] == 1:
            # Keep unique node
            prev = current
            current = current.next
        else:
            # Skip duplicate node
            prev.next = current.next
            current = current.next

    return dummy.next


# Test cases
if __name__ == "__main__":
    # Helper function to create linked list from array
    def create_list(arr):
        if not arr:
            return None
        head = ListNode(arr[0])
        current = head
        for val in arr[1:]:
            current.next = ListNode(val)
            current = current.next
        return head

    # Helper function to convert linked list to array
    def list_to_array(head):
        result = []
        current = head
        while current:
            result.append(current.val)
            current = current.next
        return result

    # Test case 1: [1,2,3,3,4,4,5]
    head1 = create_list([1, 2, 3, 3, 4, 4, 5])
    result1 = deleteDuplicates(head1)
    print(list_to_array(result1))  # [1, 2, 5]

    # Test case 2: [1,1,1,2,3]
    head2 = create_list([1, 1, 1, 2, 3])
    result2 = deleteDuplicates(head2)
    print(list_to_array(result2))  # [2, 3]

    # Test case 3: [1,1]
    head3 = create_list([1, 1])
    result3 = deleteDuplicates(head3)
    print(list_to_array(result3))  # []

C++

remove_duplicates_from_sorted_list_ii_hash_set.cpp

#include <unordered_map>
using namespace std;

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

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        /**
         * Remove all nodes with duplicate values from sorted linked list using hash set.
         *
         * Approach: Count frequency of each value, then rebuild list with unique values only.
         * Time: O(n) — two passes through the list
         * Space: O(n) — hash map stores frequencies
         */
        if (!head) return nullptr;

        // Count frequencies
        unordered_map<int, int> freq;
        ListNode* current = head;
        while (current) {
            freq[current->val]++;
            current = current->next;
        }

        // Build result list with unique values only
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* prev = dummy;
        current = head;

        while (current) {
            if (freq[current->val] == 1) {
                // Keep unique node
                prev = current;
                current = current->next;
            } else {
                // Skip duplicate node
                prev->next = current->next;
                current = current->next;
            }
        }

        ListNode* result = dummy->next;
        delete dummy;
        return result;
    }
};

// Test cases
#include <iostream>
#include <vector>

void printList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "null\n";
}

ListNode* createList(vector<int> arr) {
    if (arr.empty()) return nullptr;
    ListNode* head = new ListNode(arr[0]);
    ListNode* current = head;
    for (size_t i = 1; i < arr.size(); i++) {
        current->next = new ListNode(arr[i]);
        current = current->next;
    }
    return head;
}

int main() {
    Solution sol;

    // Test case 1: [1,2,3,3,4,4,5]
    ListNode* head1 = createList({1, 2, 3, 3, 4, 4, 5});
    cout << "Test 1: ";
    printList(sol.deleteDuplicates(head1));  // 1 -> 2 -> 5 -> null

    // Test case 2: [1,1,1,2,3]
    ListNode* head2 = createList({1, 1, 1, 2, 3});
    cout << "Test 2: ";
    printList(sol.deleteDuplicates(head2));  // 2 -> 3 -> null

    // Test case 3: [1,1]
    ListNode* head3 = createList({1, 1});
    cout << "Test 3: ";
    printList(sol.deleteDuplicates(head3));  // null

    return 0;
}

Java

remove_duplicates_from_sorted_list_ii_hash_set.java

import java.util.HashMap;
import java.util.Map;

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

class Solution {
    /**
     * Remove all nodes with duplicate values from sorted linked list using hash set.
     *
     * Approach: Count frequency of each value, then rebuild list with unique values only.
     * Time: O(n) — two passes through the list
     * Space: O(n) — hash map stores frequencies
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;

        // Count frequencies
        Map<Integer, Integer> freq = new HashMap<>();
        ListNode current = head;
        while (current != null) {
            freq.put(current.val, freq.getOrDefault(current.val, 0) + 1);
            current = current.next;
        }

        // Build result list with unique values only
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        current = head;

        while (current != null) {
            if (freq.get(current.val) == 1) {
                // Keep unique node
                prev = current;
                current = current.next;
            } else {
                // Skip duplicate node
                prev.next = current.next;
                current = current.next;
            }
        }

        return dummy.next;
    }

    // Helper function to create linked list from array
    public static ListNode createList(int[] arr) {
        if (arr.length == 0) return null;
        ListNode head = new ListNode(arr[0]);
        ListNode current = head;
        for (int i = 1; i < arr.length; i++) {
            current.next = new ListNode(arr[i]);
            current = current.next;
        }
        return head;
    }

    // Helper function to print linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        // Test case 1: [1,2,3,3,4,4,5]
        ListNode head1 = createList(new int[]{1, 2, 3, 3, 4, 4, 5});
        System.out.print("Test 1: ");
        printList(sol.deleteDuplicates(head1));  // 1 -> 2 -> 5 -> null

        // Test case 2: [1,1,1,2,3]
        ListNode head2 = createList(new int[]{1, 1, 1, 2, 3});
        System.out.print("Test 2: ");
        printList(sol.deleteDuplicates(head2));  // 2 -> 3 -> null

        // Test case 3: [1,1]
        ListNode head3 = createList(new int[]{1, 1});
        System.out.print("Test 3: ");
        printList(sol.deleteDuplicates(head3));  // null
    }
}

JavaScript

remove_duplicates_from_sorted_list_ii_hash_set.js

/**
 * Definition for singly-linked list node.
 */
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

/**
 * Remove all nodes with duplicate values from sorted linked list using hash set.
 *
 * Approach: Count frequency of each value, then rebuild list with unique values only.
 * Time: O(n) — two passes through the list
 * Space: O(n) — hash map stores frequencies
 *
 * @param {ListNode} head
 * @return {ListNode}
 */
function deleteDuplicates(head) {
    if (!head) return null;

    // Count frequencies
    const freq = new Map();
    let current = head;
    while (current) {
        freq.set(current.val, (freq.get(current.val) || 0) + 1);
        current = current.next;
    }

    // Build result list with unique values only
    const dummy = new ListNode(0);
    dummy.next = head;
    let prev = dummy;
    current = head;

    while (current) {
        if (freq.get(current.val) === 1) {
            // Keep unique node
            prev = current;
            current = current.next;
        } else {
            // Skip duplicate node
            prev.next = current.next;
            current = current.next;
        }
    }

    return dummy.next;
}

/**
 * Helper function to create linked list from array
 */
function createList(arr) {
    if (arr.length === 0) return null;
    const head = new ListNode(arr[0]);
    let current = head;
    for (let i = 1; i < arr.length; i++) {
        current.next = new ListNode(arr[i]);
        current = current.next;
    }
    return head;
}

/**
 * Helper function to print linked list
 */
function printList(head) {
    let result = '';
    while (head) {
        result += head.val + ' -> ';
        head = head.next;
    }
    result += 'null';
    console.log(result);
}

// Test cases
console.log('Test 1:');
const head1 = createList([1, 2, 3, 3, 4, 4, 5]);
printList(deleteDuplicates(head1));  // 1 -> 2 -> 5 -> null

console.log('Test 2:');
const head2 = createList([1, 1, 1, 2, 3]);
printList(deleteDuplicates(head2));  // 2 -> 3 -> null

console.log('Test 3:');
const head3 = createList([1, 1]);
printList(deleteDuplicates(head3));  // null

module.exports = { deleteDuplicates, ListNode };

Rust

remove_duplicates_from_sorted_list_ii_hash_set.rs

use std::collections::HashMap;

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}

/**
 * Remove all nodes with duplicate values from sorted linked list using hash set.
 *
 * Approach: Count frequency of each value, then rebuild list with unique values only.
 * Time: O(n) — two passes through the list
 * Space: O(n) — hash map stores frequencies
 */
pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    if head.is_none() {
        return None;
    }

    // Count frequencies
    let mut freq = HashMap::new();
    let mut current = head.as_ref();
    while let Some(node) = current {
        *freq.entry(node.val).or_insert(0) += 1;
        current = node.next.as_ref();
    }

    // Build result list with unique values only
    let mut head = head;
    let mut dummy = Box::new(ListNode::new(0));
    let mut prev = &mut dummy;

    while let Some(mut node) = head {
        head = node.next.take();
        if freq[&node.val] == 1 {
            // Keep unique node
            prev.next = Some(node);
            prev = prev.next.as_mut().unwrap();
        }
        // Skip duplicate node (don't add to result)
    }

    dummy.next.take()
}

fn main() {
    // Test case 1: [1,2,3,3,4,4,5]
    let head1 = Some(Box::new(ListNode {
        val: 1,
        next: Some(Box::new(ListNode {
            val: 2,
            next: Some(Box::new(ListNode {
                val: 3,
                next: Some(Box::new(ListNode {
                    val: 3,
                    next: Some(Box::new(ListNode {
                        val: 4,
                        next: Some(Box::new(ListNode {
                            val: 4,
                            next: Some(Box::new(ListNode {
                                val: 5,
                                next: None,
                            })),
                        })),
                    })),
                })),
            })),
        })),
    }));
    println!("Test 1: {:?}", delete_duplicates(head1));  // 1 -> 2 -> 5

    // Test case 2: [1,1,1,2,3]
    let head2 = Some(Box::new(ListNode {
        val: 1,
        next: Some(Box::new(ListNode {
            val: 1,
            next: Some(Box::new(ListNode {
                val: 1,
                next: Some(Box::new(ListNode {
                    val: 2,
                    next: Some(Box::new(ListNode {
                        val: 3,
                        next: None,
                    })),
                })),
            })),
        })),
    }));
    println!("Test 2: {:?}", delete_duplicates(head2));  // 2 -> 3

    // Test case 3: [1,1]
    let head3 = Some(Box::new(ListNode {
        val: 1,
        next: Some(Box::new(ListNode {
            val: 1,
            next: None,
        })),
    }));
    println!("Test 3: {:?}", delete_duplicates(head3));  // null
}

Go

remove_duplicates_from_sorted_list_ii_hash_set.go

package main

import "fmt"

type ListNode struct {
  Val  int
  Next *ListNode
}

/**
 * Remove all nodes with duplicate values from sorted linked list using hash set.
 *
 * Approach: Count frequency of each value, then rebuild list with unique values only.
 * Time: O(n) — two passes through the list
 * Space: O(n) — hash map stores frequencies
 */
func deleteDuplicates(head *ListNode) *ListNode {
  if head == nil {
    return nil
  }

  // Count frequencies
  freq := make(map[int]int)
  current := head
  for current != nil {
    freq[current.Val]++
    current = current.Next
  }

  // Build result list with unique values only
  dummy := &ListNode{Val: 0}
  dummy.Next = head
  prev := dummy
  current = head

  for current != nil {
    if freq[current.Val] == 1 {
      // Keep unique node
      prev = current
      current = current.Next
    } else {
      // Skip duplicate node
      prev.Next = current.Next
      current = current.Next
    }
  }

  return dummy.Next
}

// Helper function to create linked list from array
func createList(arr []int) *ListNode {
  if len(arr) == 0 {
    return nil
  }
  head := &ListNode{Val: arr[0]}
  current := head
  for i := 1; i < len(arr); i++ {
    current.Next = &ListNode{Val: arr[i]}
    current = current.Next
  }
  return head
}

// Helper function to print linked list
func printList(head *ListNode) {
  for head != nil {
    fmt.Printf("%d -> ", head.Val)
    head = head.Next
  }
  fmt.Println("null")
}

func main() {
  // Test case 1: [1,2,3,3,4,4,5]
  head1 := createList([]int{1, 2, 3, 3, 4, 4, 5})
  fmt.Print("Test 1: ")
  printList(deleteDuplicates(head1))  // 1 -> 2 -> 5 -> null

  // Test case 2: [1,1,1,2,3]
  head2 := createList([]int{1, 1, 1, 2, 3})
  fmt.Print("Test 2: ")
  printList(deleteDuplicates(head2))  // 2 -> 3 -> null

  // Test case 3: [1,1]
  head3 := createList([]int{1, 1})
  fmt.Print("Test 3: ")
  printList(deleteDuplicates(head3))  // null
}

Watch for these pitfalls

• Dummy node is essential: If the head itself is part of a duplicate group, the dummy becomes the safe starting point.
• Advancing current vs prev: In single-pass, when you skip duplicates, only current moves; prev stays until a unique node is found.
• Null pointer checks: Always verify current.next != null before comparing values to avoid crashes.
• Forgetting the second skip: When skipping duplicates, you must advance current through all matching values, not just to the next node.

Approach 3: Optimized Two-Pointer

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

remove_duplicates_from_sorted_list_ii_optimized.py

"""
Solution for Remove Duplicates from Sorted List II
"""

def solve():
    """Implementation for approach 3 of Remove Duplicates from Sorted List II"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

remove_duplicates_from_sorted_list_ii_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Remove Duplicates from Sorted List II
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

RemoveDuplicatesFromSortedListIiOptimized.java

/**
 * Solution for Remove Duplicates from Sorted List II
 * Approach 3
 */
public class RemoveDuplicatesFromSortedListIiOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

remove_duplicates_from_sorted_list_ii_optimized.js

/**
 * Solution for Remove Duplicates from Sorted List II
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

remove_duplicates_from_sorted_list_ii_optimized.rs

/// Solution for Remove Duplicates from Sorted List II
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

remove_duplicates_from_sorted_list_ii_optimized.go

package main

import "fmt"

// Solution for Remove Duplicates from Sorted List II
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Remove Duplicates from Sorted List Easy #83
• Merge Two Sorted Lists ↗ Easy #21
• Reverse Linked List ↗ Easy #206
• Reverse Linked List II ↗ Medium #92

Interview Tips

Key trade-offs to discuss

• Single-pass benefit: O(1) space is ideal when memory is constrained.
• Hash set benefit: Two separate passes make the logic clearer and easier to debug.
• Dummy node insight: Using a sentinel node simplifies edge cases (e.g., duplicate at head).
• When to use which: Ask the interviewer about space constraints; if O(n) space is acceptable, the hash set approach is easier to code error-free.
• Edge case: A list of all duplicates (e.g., 1 → 1 → 1) should return an empty list—verify this works in your implementation.

← Previous
#80 Remove Duplicates from Sorted Array II Next
#86 Partition List →