Remove Duplicate Nodes Linked List — Problem Statement & Solution Guide

Linked ListEasyTwo Pointers

TimeO(n)

SpaceO(1)

Problem Description

Given the head of a singly linked list whose node values are sorted in non‑decreasing order, modify the list in place so that each distinct value appears exactly once. The function should return the head of the resulting list. No new nodes may be allocated; you may only adjust the next pointers of existing nodes. The input list may contain any integer values within the allowed range, and it may consist of a single node.

DSA Pattern Breakdown

"Remove Duplicate Nodes Linked List"

easy

WHY DOES IT MATTER?

The "in‑place deduplication of sorted data" pattern appears in many low‑level system components—such as log compaction, memory deduplication, and stream processing—where minimizing memory churn is critical for performance and scalability.

OPTIMIZATION CHALLENGE

The key insight is recognizing that sorted order guarantees adjacency of duplicates, allowing a single linear pass with only pointer rewiring, eliminating the need for extra data structures or multiple traversals.

REAL-WORLD CONNECTION

Think of a distributed log where entries are appended in order; compaction removes consecutive duplicate entries to shrink storage, mirroring how we collapse adjacent duplicate nodes in a linked list.

During an interview, start by stating the sorted‑list property, then sketch the two‑pointer loop on the whiteboard before writing code; this demonstrates both conceptual clarity and practical implementation skill.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem leverages the fundamental property of a sorted singly linked list: duplicate values appear consecutively. By traversing the list once and comparing each node's value with its immediate successor, we can decide whether to keep or bypass the next node. This in‑place elimination avoids any allocation overhead, preserving the original memory footprint. Naïve solutions that allocate a new list or use auxiliary hash structures break the O(1) space guarantee and become costly for very long lists, especially when the input size reaches millions of nodes. The optimal paradigm is a two‑pointer technique—often called the "slow‑fast" or "current‑next" approach—where the current pointer anchors the unique sub‑list while the next pointer scans ahead, stitching together only distinct values. This yields linear time complexity because each node is visited exactly once, and constant auxiliary space because no extra containers are created.

Interview Questions on This Problem

Q1How would you modify the algorithm if the list were NOT sorted?

You would need to detect duplicates using a hash set to track seen values, iterating through the list and removing a node when its value already exists in the set. This changes the space complexity to O(n) while preserving O(n) time.

Q2Can you explain why removing duplicates in a sorted linked list can be done in O(1) extra space?

Because duplicates are guaranteed to be adjacent, we can decide to skip a node solely by looking at its next neighbor, adjusting pointers without storing any additional information about previously seen values.

Q3What edge cases must you handle when implementing this in a production codebase?

You must correctly handle an empty list, a single‑node list, and cases where the last several nodes are duplicates, ensuring the tail pointer is updated to null after removals.

Examples

Example 1

Input

[1,1,2,3,3]

Output

[1,2,3]

Explanation: Start at the first node (value 1). The next node also holds 1, so skip it by linking the first node directly to the node with value 2. Continue: 2's next is 3, which is different, so keep it. The following node is another 3, duplicate of the previous, so bypass it. The final list is 1 → 2 → 3.

Example 2

Input

[2,2,2,2]

Output

[2]

Explanation: All nodes contain the same value 2. The first node is kept, and each subsequent node is removed by linking the first node directly to null. The resulting list contains a single node with value 2.

Example 3

Input

[-3,-3,-1,0,0,5]

Output

[-3,-1,0,5]

Explanation: Traverse from the head: first -3 is kept, next -3 is duplicate and removed. -1 differs from -3, so it stays. 0 follows -1 and is kept; the next 0 is duplicate and removed. Finally, 5 differs from 0 and remains. The cleaned list is -3 → -1 → 0 → 5.

Constraints

1 <= number of nodes <= 10^5
-10^9 <= node.val <= 10^9
The values are sorted in non‑decreasing order
The algorithm must run in O(n) time and O(1) extra space

Optimal Approach & Strategy

Traverse the list once with two pointers: one for the last unique node and one for the candidate node. If values differ, link them; otherwise, bypass the duplicate. This runs in O(n) time and O(1) extra space.

Brute Force Approach

A naive method would copy each node into a new list while checking every previous node for the same value, resulting in O(n^2) time. It also allocates new nodes, violating the in‑place constraint.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

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

class Solution {
   public:
     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;
     }
   }

class Solution {
     public 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;
     }
   }

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

   def deleteDuplicates(self, 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

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

Asked in Top Tech Interviews

AdobeAmazonUber

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Remove Duplicate Nodes Linked List Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Linked List

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Remove Duplicate Nodes Linked List — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor