Remove Duplicates from Sorted List II

class Solution {
public:
    ListNode* removeDuplicates(ListNode* start) {
        ListNode* fakeHead = new ListNode(0, start);
        ListNode* previous = fakeHead;
    
        while (start != NULL) {
            if (start->next != NULL && start->val == start->next->val) {
                while (start->next != NULL && start->val == start->next->val) {
                    start = start->next;
                }
                previous->next = start->next;
            } else {
                previous = previous->next;
            }
            start = start->next;
        }
        return fakeHead->next;
    }
};

The solution provided is a C++ implementation that efficiently removes all duplicate nodes from a sorted linked list, where the list is ordered in non-decreasing order. This is accomplished by retaining only those nodes that do not have a duplicate entry. Here is a step-by-step breakdown of how the solution operates:

1. Create an auxiliary 'fakeHead' node. This node points to the start of the actual list, facilitating the handling of edge cases, such as when the initial nodes are duplicates.

2. Initialize a pointer 'previous' at 'fakeHead' to track the last node in the sequence of unique nodes.

3. Iterate through the list starting from the head. Use the pointer 'start' for traversal.

4. Check if the current node ('start') and its successor ('start->next') have the same value. If they do, continue moving 'start' forward until the end of the duplicates sequence is found.

5. Once the end of the duplicates sequence is reached, connect the 'previous' node to the node following the last duplicate ('start->next'), effectively skipping over all the duplicates.

6. If 'start' and 'start->next' are not duplicates, move the 'previous' pointer to 'previous->next' (which points to 'start').

7. Move 'start' to 'start->next' to check the next set of elements.

8. After the loop, return the next node to 'fakeHead', which is the start of the modified list free of duplicates.

This approach ensures a robust solution with a time complexity dominantly governed by the linear traversal of the list, thereby accomplishing the removal operation efficiently in-place.

class Solution {
    public ListNode removeDuplicates(ListNode headNode) {
        ListNode initialNode = new ListNode(0, headNode);
        ListNode lastUnique = initialNode;
    
        while (headNode != null) {
            if (headNode.next != null && headNode.val == headNode.next.val) {
                while (headNode.next != null && headNode.val == headNode.next.val) {
                    headNode = headNode.next;
                }
                lastUnique.next = headNode.next;
            } else {
                lastUnique = lastUnique.next;
            }
            headNode = headNode.next;
        }
        return initialNode.next;
    }
}

The provided Java solution aims to remove all elements that appear more than once in a sorted linked list, ensuring that no duplicates remain. The approach involves maintaining pointers to traverse through the linked list and handle duplicates effectively. Here’s a breakdown of the operations performed in the code to understand the functionality better:

• Create a placeholder node (initialNode) pointing to the head of the list. This node helps in easily returning the modified list without handling edge cases where the head might be removed.
• Use a pointer lastUnique to track the last node in the list that confirmedly has no duplicates.
• Traverse the list using the headNode pointer. During each iteration, check for duplicates by comparing the node's value with its next node's value.
• If a duplicate is detected (headNode.val == headNode.next.val), skip all consecutive nodes that have the same value.
• Adjust the lastUnique.next to connect with the next node after the last duplicate.
• If no duplicate is found, move the lastUnique pointer one step forward.
• Continue the process until headNode traverses all nodes.
• Return the next node of initialNode, which is the head of the modified list without duplicates.

Execute this block of code to modify a sorted linked list by removing all elements that are duplicated, leaving only distinct numbers that originally appeared in the list. Make sure to handle edge cases like an empty list or a list where all elements are the same.

struct ListNode* removeDuplicates(struct ListNode* start) {
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->val = 0;
    dummy->next = start;
        
    struct ListNode* previous = dummy;
        
    while (start != NULL) {
        if (start->next != NULL && start->val == start->next->val) {
            while (start->next != NULL && start->val == start->next->val) {
                start = start->next;
            }
            previous->next = start->next;
        } else {
            previous = previous->next;
        }
        start = start->next;
    }
    return dummy->next;
}

The provided C code defines a function to remove all elements from a sorted linked list that have duplicates. The function is named removeDuplicates and it takes a pointer to the first node of a linked list as its parameter. The function's goal is to ensure that each value in the linked list appears exactly once, removing any duplicates entirely, not just their additional occurrences.

Here's a breakdown of the steps the function takes:

1. Create a dummy node, which will help in easily removing nodes at the beginning of the list if they are duplicates. This dummy node initially points to the start of the list.

2. Use two pointers:

   • previous – Starts at the dummy node.
   • start – Used to traverse the list.

3. Iterate through the list with the start pointer. For each node:

   • Check if the current node and the next node have the same value. If so, there are duplicates, and you find the last node in this sequence of duplicates.
   • Update previous->next to skip over all the detected duplicates.
   • If no duplicates are found, simply move the previous pointer to the next node.

4. Return the modified list, which starts after the dummy node.

This solution effectively handles the removal of duplicates by skipping over all nodes that have the same value consecutively in the list. After using this function, the returned linked list will have only unique elements remaining from the original list, each appearing exactly once.

var removeDuplicates = function (firstNode) {
    let initial = new ListNode(0, firstNode);
    let previous = initial;
    while (firstNode !== null) {
        if (firstNode.next !== null && firstNode.val === firstNode.next.val) {
            while (firstNode.next !== null && firstNode.val === firstNode.next.val) {
                firstNode = firstNode.next;
            }
            previous.next = firstNode.next;
        } else {
            previous = previous.next;
        }
        firstNode = firstNode.next;
    }
    return initial.next;
};

The provided solution effectively removes duplicates from a sorted linked list using JavaScript. Here's how it accomplishes this:

• Initialize a new list node (initial) with zero as a value and firstNode as its next node to simplify edge cases handling (head duplicates).
• Use a pointer previous to keep track of the last node before the duplicate sequence starts.
• Iterate over the list starting from the first node. The loop continues until there are no more nodes to examine (firstNode becomes null).
• Check if the current node (firstNode) has a duplicate immediately next (firstNode.val === firstNode.next.val). If duplicates are found:
  • Continue to traverse until the end of duplicates.
  • Set the previous.next to point to the node right after the last duplicate, effectively skipping the entire sequence of duplicate values.
• If no duplicates are detected for the current node, simply move the previous pointer to previous.next.
• After ending the duplication check loop, the pointer firstNode also moves to the next node.
• Return initial.next, which points to the head of the modified list where all duplicates have been removed.

This approach ensures that all nodes with values that appear more than once in the sorted linked list are completely removed, leaving only distinct values.

class Solution:
    def removeDuplicates(self, start: ListNode) -> ListNode:
        # Create initial node
        initial = ListNode(0, start)
    
        # Previous node tracker
        previous = initial
    
        while start:
            # Check for the start of duplicates
            if start.next and start.val == start.next.val:
                # Find the end of duplicates
                while start.next and start.val == start.next.val:
                    start = start.next
                # Connect to the next new value
                previous.next = start.next
            else:
                # Move the previous pointer
                previous = previous.next
    
            # Proceed to next node
            start = start.next
    
        return initial.next

The provided Python solution works to remove duplicates from a sorted linked list where numbers that appear more than once are all removed completely. Here's a breakdown of how the code accomplishes this:

1. Define a dummy or sentinel node, initial, and set its next pointer to the head of the list, start. This node helps easily manage nodes at the head of the list.
2. Use a previous point which initially points to this dummy node. This helps in easily connecting and managing the preceding nodes.
3. Iterate through the linked list using a while loop on start.
4. Inside the loop, check if the current node (start) and its next node (start.next) have the same value, indicating the start of a sequence of duplicates.
   • If they do, skip all nodes in this sequence by continuing to move the start pointer as long as subsequent nodes have the same value.
   • Once the end of duplicates is reached, make the previous.next point to start.next, effectively skipping over all the duplicates.
5. If the current node is not a duplicate, simply move the previous pointer to the current node (start), thus keeping it linked to the non-duplicate sequence.
6. Continuously move start to the next node in the list.
7. Finally, return the new list starting from the node right after the dummy node (initial.next), which represents the head of the modified list.

This method efficiently handles the removal of all nodes in the list that have duplicate values and retains only those nodes that appear exactly once.