Solution Explanation for Remove Duplicates from Sorted List

This problem involves removing duplicate nodes from a sorted linked list, ensuring that each value appears only once while maintaining the sorted order. The optimal approach is a single-pass iteration.

Algorithm:

1. Initialization: We start with a pointer cur pointing to the head of the linked list.

2. Iteration: We iterate through the list as long as cur is not null (end of list) and cur.next is not null (to avoid accessing beyond the list).

3. Duplicate Check: Inside the loop, we compare the value of the current node (cur.val) with the value of the next node (cur.next.val).

4. Duplicate Removal: If the values are equal (a duplicate is found), we bypass the duplicate node by updating cur.next to point directly to the node after the duplicate (cur.next.next).

5. Advance Pointer: If the values are different (no duplicate), we simply move the cur pointer to the next node (cur = cur.next) to continue the iteration.

6. Return: After the loop completes, the list is modified in place, with duplicates removed. We return the original head of the list.

Time Complexity: O(n) - We iterate through the linked list once, where 'n' is the number of nodes.

Space Complexity: O(1) - We use a constant amount of extra space (only the cur pointer).

Code Examples:

The code implementations in various languages follow the same algorithmic structure:

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]:
        cur = head
        while cur and cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

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 cur = head;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }
}

C++:

/**
 * 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) {
        ListNode* cur = head;
        while (cur != nullptr && cur->next != nullptr) {
            if (cur->val == cur->next->val) {
                cur->next = cur->next->next;
            } else {
                cur = cur->next;
            }
        }
        return head;
    }
};

(Other languages like Go, Rust, Javascript, and C# are provided in the original response and follow the same logic with only syntax variations)

This single-pass approach is efficient and effectively removes duplicates from a sorted linked list without requiring additional data structures.