Frontend School

Remove Duplicates from Sorted Linked List

DSA
easy

Remove Duplicates from Sorted Linked List

Easy
Linked List
Two Pointers

Overview

In many data processing systems, maintaining clean and unique records is crucial. Imagine you're processing a stream of user activity logs or sensor data that has already been sorted by a key, but due to system glitches or re-transmissions, duplicate entries might appear consecutively. Your task is to clean up such a list, ensuring that each unique data point is represented exactly once while preserving the original sorted order.

What you need to do / Task

Given the head of a sorted singly-linked list, delete all duplicate nodes such that each element appears only once. The resulting list must also be sorted.

Input & output

Input:

  • head: A ListNode representing the head of a sorted singly-linked list. The list can be empty (null).

Output:

  • A ListNode representing the head of the modified sorted linked list with all duplicates removed. If the input list was empty, return null.

ListNode Definition:

class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.next = (next===undefined ? null : next)
    }
}

Clarifications

  • Empty list: If head is null, return null.
  • Single node list: If the list contains only one node, it has no duplicates, so return the head as is.
  • All duplicates: If all elements in the list are duplicates (e.g., [1,1,1,1]), the output should contain only one instance of that element (e.g., [1]).

Examples

1

Example 1

Input:

head = [1,1,2]

Output:

[1,2]

Note:

The duplicate '1' is removed, leaving '1' and '2'.

2

Example 2

Input:

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

Output:

[1,2,3]

Note:

Duplicate '1's are reduced to a single '1', and duplicate '3's are reduced to a single '3'.

3

Example 3

Input:

head = [1,1,1,1]

Output:

[1]

Note:

All '1's are duplicates, so only one '1' remains.

Constraints

Constraints & assumptions

  • 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 non-decreasing order.

What interviewers evaluate

  • Correctness: Your solution should handle all edge cases, including empty lists, single-node lists, lists with no duplicates, and lists where all elements are duplicates.
  • Efficiency: The solution should ideally run in linear time complexity (O(N)) and constant space complexity (O(1)).
  • Code Quality: Demonstrated ability to write clean, readable, and well-structured code with appropriate variable names.
  • Problem Solving: Your approach to traversing and modifying the linked list using pointers effectively.

Loading editor...