💬 Discord
Sign In
NeetCode #308LC-83EasyLinked List
← Back to All Problems

#308 · #83 · Remove Duplicates from Sorted List(删除排序链表中的重复元素)

📌 Problem Statement & Constraints

Given the head of a sorted linked list, delete all duplicates so each value appears once, and return the head. Constraints: the number of nodes is in [0, 300], -100 <= Node.val <= 100.

💡 Core Algorithmic Approaches

  1. Because the list is sorted, duplicates are adjacent.
  2. Walk with a single pointer: if the successor has the same value, unlink it; otherwise advance.
  3. Unlinking without advancing is essential, since the new successor may also be a duplicate (runs longer than two).
  4. This is the linked-list analogue of Remove Duplicates from a sorted array.

💻 Benchmark Python3 Implementation

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        while cur and cur.next:
            if cur.next.val == cur.val:
                cur.next = cur.next.next   # unlink the duplicate
            else:
                cur = cur.next
        return head

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(1): pointer manipulation only.

⚠️ Interview Pitfalls & Follow-ups

  • Advancing after unlinking: a run of three or more equal values would leave duplicates behind.
  • Comparing cur.val with cur.next.next.val: that skips the immediate successor.
  • Using a hash set: unnecessary given the sortedness, and it would use O(n) space.
  • Returning dummy.next: no dummy is needed here, since the head is never removed.