Solution Explanation: Removing Duplicates from a Sorted Linked List II

This problem requires removing duplicate nodes from a sorted linked list, leaving only unique values. The solution presented uses a single pass through the list, optimizing for time and space complexity.

Approach:

The algorithm cleverly utilizes two pointers, pre and cur, to iterate through the list. A dummy node is prepended to simplify handling the head of the list.

1. Initialization:

   • A dummy node dummy is created and linked to the head of the input list (head). This simplifies edge case handling (empty list or duplicates at the beginning).
   • pre points to the dummy node.
   • cur points to the head of the list.

2. Iteration: The while cur loop iterates until the end of the list is reached.

3. Duplicate Detection: The inner while loop (while cur.next and cur.next.val == cur.val) efficiently identifies consecutive duplicate nodes. It moves cur forward until a unique value is encountered.

4. Decision Making: After the inner loop, there are two scenarios:

   • No Duplicates: If pre.next == cur, it means no duplicates were found between pre and cur. In this case, pre is simply advanced to cur to continue the process.
   • Duplicates Found: If pre.next != cur, duplicates existed. pre.next is updated to skip the duplicate segment by pointing directly to cur.next. This effectively removes the duplicates.

5. Iteration Continuation: cur is advanced to the next node to continue the process.

6. Return Value: Finally, dummy.next is returned, which points to the head of the modified list (without the dummy node).

Time Complexity Analysis:

The outer loop iterates through each node in the linked list once. The inner loop iterates only over consecutive duplicate nodes, which collectively contribute to at most n iterations. Therefore, the overall time complexity is O(n), where n is the number of nodes in the list.

Space Complexity Analysis:

The algorithm uses a constant amount of extra space (for the pointers pre, cur, and the dummy node). Thus, the space complexity is O(1).

Code Examples (Python & Java):

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]:
        dummy = pre = ListNode(next=head)  # Create dummy node
        cur = head
        while cur:
            while cur.next and cur.next.val == cur.val:
                cur = cur.next
            if pre.next == cur:
                pre = cur
            else:
                pre.next = cur.next
            cur = cur.next
        return dummy.next
 

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) {
        ListNode dummy = new ListNode(0, head); //Create Dummy Node
        ListNode pre = dummy;
        ListNode cur = head;
        while (cur != null) {
            while (cur.next != null && cur.next.val == cur.val) {
                cur = cur.next;
            }
            if (pre.next == cur) {
                pre = cur;
            } else {
                pre.next = cur.next;
            }
            cur = cur.next;
        }
        return dummy.next;
    }
}

The other languages provided (C++, Go, TypeScript, Rust, JavaScript, C#) implement essentially the same algorithm with minor syntactic differences. The core logic of using a dummy node and two pointers to efficiently identify and remove duplicate nodes remains consistent.