Given the head of a sorted linked list, delete all duplicates such that each element appears only once.
Return the head of the updated linked list.
Example 1:
Input: head -> 1 -> 2 -> 3 -> 3 -> 3 -> 4
Output: head -> 1 -> 2 -> 3 -> 4
Solve Here: Leetcode 83
Intuition
Since the linked list is sorted, duplicate elements will always appear next to each other.
Therefore, for any give node, we only need to compare it with its immediate next node. If both values are equal, we can safely skip the next node by updating the current node's pointer.
Algorithm
Iterate through the linked list while the current node and its next node exist.
For each node, compare its value with the value of the next node. If they are equal, update the current node's next pointer to skip the duplicate node. Otherwise, move the current pointer forward.
public ListNode deleteDuplicates(ListNode head) {
// Step 1: Check if list is empty
if (head == null) return head;
ListNode current = head;
while (current != null && current.next != null) {
// Step 2: Check for duplicate entries
if (current.val == current.next.val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return head;
}
Visualization
Time Complexity
We are iterating through the linked list once. Hence, the overall time complexity = O(n).
Space Complexity
We are not using any extra space. Hence, the overall space complexity = O(1).