Question
Formatted question description: https://leetcode.ca/all/82.html
82 Remove Duplicates from Sorted List II
Given a sorted linked list, delete all nodes that have duplicate numbers,
leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
@tag-linkedlist
Algorithm
Here we need to delete all the duplicates. Because there may be duplicates at the beginning of the linked list, the head pointer will change if it is deleted, but the head pointer of the linked list needs to be returned in the end.
Therefore, you need to define a new node, then link the original linked list, and then define a precursor pointer and a current pointer. Each current pointer points to the newly created node. The current pointer starts from the next position and traverses down.
- If the same is encountered, it will continue. Next, until a different item is encountered, the next of the predecessor pointer points to the different element below.
- If the first element traversed by the current pointer is not the same, move the predecessor pointer down one place.
Code
Java
public class Remove_Duplicates_from_Sorted_List_II {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
ListNode current = head;
while (current != null) {
boolean dup = false;
// probe next to see if duplicate
while (current.next != null && current.val == current.next.val) {
current = current.next;
dup = true;
}
if (dup) { // prev staying the same
prev.next = current.next;
current = current.next;
} else {
prev = current;
current = current.next;
}
}
return dummy.next;
}
}