Why it fails (or is suboptimal): While this approach produces the correct output, it fails to meet the efficiency standards of a senior-level interview.

• Space Complexity: It requires O(N) space to store the frequency map and potentially O(N) space for the new list nodes. The problem implies an in-place solution is preferred.
• Inefficiency: It requires two full passes over the data and ignores the advantage that the input list is already sorted.

Core Insight for Remove Duplicates from Sorted List II

The core insight relies on the fact that the input list is sorted. This guarantees that all duplicates of a specific value are grouped together contiguously. We do not need a global frequency count; we only need to look at the immediate neighborhood of the current node.

To solve this in-place, we utilize the pointer manipulation techniques found in reversal algorithms. Specifically, we maintain a prev pointer that acts as an anchor. As we scan forward with curr, if we detect a sequence of duplicates, we do not advance prev. Instead, we fast-forward curr past the duplicates and then strictly rewire prev.next to point to the new curr. This effectively excises the sub-segment of duplicates.

This requires a Sentinel Node (Dummy Head). Since the head of the list itself might be a duplicate (e.g., 1 -> 1 -> 2), it might need to be removed. A sentinel node ensures that head is never a special case; prev can always start at the sentinel.

Visual Description: Imagine the list as a chain. We hold the link before a potential duplicate group (prev). We send a scout (head or curr) forward. If the scout sees identical values ahead, it keeps running until the values change. Once the scout lands on a distinct value (or null), we disconnect the chain at prev and snap it directly to the scout's new position, dropping the entire segment of duplicates into garbage collection.

Execution Flow

Let's trace the algorithm with Input: 1 -> 2 -> 3 -> 3 -> 4.

1. Setup:

   • sentinel -> 1 -> 2 -> 3 -> 3 -> 4
   • prev points to sentinel.
   • head points to 1.

2. Iteration 1 (head = 1):

   • Check head.val (1) vs head.next.val (2). Different.
   • Node 1 is distinct.
   • Advance prev to 1.
   • Advance head to 2.

3. Iteration 2 (head = 2):

   • Check head.val (2) vs head.next.val (3). Different.
   • Node 2 is distinct.
   • Advance prev to 2.
   • Advance head to 3.

4. Iteration 3 (head = 3):

   • Check head.val (3) vs head.next.val (3). Duplicate detected.
   • Enter skipping mode.
   • While head.next exists and equals 3, move head.
   • head moves to the second 3.
   • Now head.next is 4 (distinct).
   • Rewire: Set prev.next (currently node 2's next) to head.next (node 4).
   • The link 2 -> 3 -> 3 is broken. It is now 2 -> 4.
   • Advance head to .

5. Iteration 4 (head = 4):

   • Check head.val (4) vs head.next (null). No duplicate.
   • Advance prev to 4.
   • Advance head to null.

6. Termination:

   • head is null. Loop ends.
   • Return sentinel.next (1 -> 2 -> 4).

Proof of Correctness

The algorithm's correctness relies on the sorted invariant. Because the list is sorted, duplicates are strictly adjacent. By checking head.val == head.next.val, we can greedily identify the start of a duplicate sequence. By advancing head until the values differ, we identify the end of that sequence.

The usage of the sentinel node guarantees that we can always perform the prev.next = ... operation, even if the entire list consists of duplicates (resulting in an empty list) or if the head is removed. The logic ensures prev is only advanced when a node is confirmed unique, maintaining the integrity of the result list.

Reference Implementation

C++ Solution for LeetCode 82

cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head || !head->next) return head;

        // Sentinel node to handle edge cases where head is deleted
        ListNode* sentinel = new ListNode(0, head);
        ListNode* prev = sentinel;
        
        while (head) {
            // If current node is a duplicate
            if (head->next && head->val == head->next->val) {
                // Move head until the end of the duplicates
                while (head->next && head->val == head->next->val) {
                    head = head->next;
                }
                // Skip all duplicates
                prev->next = head->next;
            } else {
                // No duplicate, move prev forward
                prev = prev->next;
            }
            // Move head to the next node to process
            head = head->next;
        }
        
        ListNode* result = sentinel->next;
        delete sentinel; // Cleanup memory
        return result;
    }
};

Java Solution for LeetCode 82

java
/**
 * Definition for singly-linked list.
 * public 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 {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;

        // Sentinel node prevents loss of head reference
        ListNode sentinel = new ListNode(0, head);
        ListNode prev = sentinel;
        
        while (head != null) {
            // Check if current node is the start of duplicates
            if (head.next != null && head.val == head.next.val) {
                // Loop until the last node of the duplicate sequence
                while (head.next != null && head.val == head.next.val) {
                    head = head.next;
                }
                // Rewire prev to skip the duplicates entirely
                prev.next = head.next;
            } else {
                // If distinct, prev can safely advance
                prev = prev.next;
            }
            // Move head forward to continue scanning
            head = head.next;
        }
        
        return sentinel.next;
    }
}

Python Solution for LeetCode 82

python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Sentinel node handles the case where the head itself is a duplicate
        sentinel = ListNode(0, head)
        prev = sentinel
        
        while head:
            # Check if we have a duplicate sequence
            if head.next and head.val == head.next.val:
                # Move head until we reach the last node of the duplicate set
                while head.next and head.val == head.next.val:
                    head = head.next
                # Wire prev to the node AFTER the duplicates
                prev.next = head.next
            else:
                # Current node is distinct, move prev forward
                prev = prev.next
                
            # Move head forward for the next iteration
            head = head.next
            
        return sentinel.next