Remove Duplicates from Linked List

You're given the head of a Singly Linked List whose nodes are in sorted order with respect to their values. Write a function that returns a modified version of the Linked List that doesn't contain any nodes with duplicate values. The Linked List should be modified in place (i.e., you shouldn't create a brand new list), and the modified Linked List should still have its nodes sorted with respect to their values. Each LinkedList node has an integer value as well as a next node pointing to the next node in the list or to None / null if it's the tail of the list.

Sample Input linkedList = 1 - 1 - 3 - 4 - 4 - 4 - 5 - 6 - 6

Sample Output 1 - 3 - 4 - 5 - 6

Solution 1: Hash set#

Track every value we have seen in a hash set. Walk the list with a curr pointer and a prev pointer; when curr->value is already in the set, bypass curr by setting prev->next = curr->next. When the value is new, add it to the set and advance prev. This works on unsorted lists too, but requires O(n) extra space — unnecessary here since the list is already sorted.

• Use Hash set to store the discovered nodes
• If a value appears again → remove that node.

#include <unordered_set>
using namespace std;

LinkedList* removeDuplicatesFromLinkedList(LinkedList* linkedList) {
    if (!linkedList) return nullptr;

    unordered_set<int> seen;

    LinkedList* curr = linkedList;
    LinkedList* prev = nullptr;

    while (curr) {
        // If value already exists, remove node
        if (seen.count(curr->value)) {
            prev->next = curr->next;
        }
        // If first time seen
        else {
            seen.insert(curr->value);
            prev = curr;
        }

        curr = curr->next;
    }

    return linkedList;
}

Time Complexity: O(n)

Space Complexity: O(n)

Solution 2: Two Pointers#

Because the list is sorted, all duplicates of a value are contiguous. node anchors the last unique node we have committed to the result, while front scouts ahead. Whenever front->value != node->value, we found a new unique value: wire node->next = front and advance node. When front reaches a duplicate, we simply advance front without rewiring. At the end, we set node->next = nullptr (or whatever front settled on) to terminate the cleaned list. O(n) time, O(1) space — no hash set needed.

• We use two pointers:
  • front → moves ahead and checks every node.
  • node → always stays at the last unique value we have kept.

using namespace std;

// This is an input struct. Do not edit.
class LinkedList {
 public:
  int value;
  LinkedList* next = nullptr;

  LinkedList(int value) { this->value = value; }
};

LinkedList* removeDuplicatesFromLinkedList(LinkedList* linkedList) {
  if(!linkedList)
    return nullptr;

  LinkedList* front = linkedList->next;
  LinkedList* node = linkedList;

  while(front){
    if(front->value != node->value){
      node->next = front;
      node = front;
    }
    front = front->next;
  }

  node->next = front;
  return linkedList;
}

Time Complexity: O(n)

Space Complexity: O(1)

Solution 3: Single Pointer#

The cleanest solution: a single pointer node walks the list. While node->next exists and has the same value as node, we skip node->next by setting node->next = node->next->next (and we continue without advancing node, because the newly attached next might be another duplicate). Only when the values differ do we advance node. This is the most concise way to exploit the sorted-list property and runs in O(n) time and O(1) space.

• If the current node and the next node have the same value,
• just skip the next node.

using namespace std;

// This is an input struct. Do not edit.
class LinkedList {
 public:
  int value;
  LinkedList* next = nullptr;

  LinkedList(int value) { this->value = value; }
};

LinkedList* removeDuplicatesFromLinkedList(LinkedList* linkedList) {
  if(!linkedList)
    return nullptr;

  LinkedList* node = linkedList;

  while(node->next){
    if(node->value == node->next->value){
      node->next = node->next->next;
      continue;
    }
    node = node->next;
  }

  return linkedList;
}

Time Complexity: O(n)

Space Complexity: O(1)