Remove Duplicates from Sorted List
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.
Example 1:
Input: head = [1,1,2]
Output: [1,2]
Example 2:
Input: head = [1,1,2,3,3]
Output: [1,2,3]
Constraints:
The number of nodes in the list is in the range [0, 300].
-100 <= Node.val <= 100
The list is guaranteed to be sorted in ascending order.
My Solution
We can solve this with one pass through the list. First off, looking at the constraints, the number of nodes in the list can be 0, so we have to handle that special case. Otherwise, we just solve this with two pointers. The first pointer starts at the first element. The second pointer points at the second element. At every iteration we check to see if the first pointer equals the second pointer. If it does, we just increment the second pointer because we don’t want to include that duplicated element. If it doesn’t, we set the next of the first pointer to the second pointer and move both pointers forward. Finally we exit the loop when the second pointer is null and at this point we just need to set the next pointer of the first pointer to null and return the original head.
Time complexity is O(n) because we are iterating once through the list. Space complexity is O(1), since we only require constant extra memory.
/**
* 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;
}
ListNode n1 = head;
ListNode n2 = head.next;
while (n1 != null && n2 != null) {
if (n1.val != n2.val) {
n1.next = n2;
n1 = n1.next;
n2 = n2.next;
}
else {
n2 = n2.next;
}
}
n1.next = null;
return head;
}
}