LeetCode-in-Java
82. Remove Duplicates from Sorted List II
Medium
Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.
Example 1:
Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]
Example 2:
Input: head = [1,1,1,2,3]
Output: [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.
Solution
import com_github_leetcode.ListNode;
/*
* 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; }
* }
*/
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(0);
ListNode prev = dummy;
prev.next = head;
ListNode curr = head.next;
while (curr != null) {
boolean flagFoundDuplicate = false;
while (curr != null && prev.next.val == curr.val) {
flagFoundDuplicate = true;
curr = curr.next;
}
if (flagFoundDuplicate) {
prev.next = curr;
if (curr != null) {
curr = curr.next;
}
} else {
prev = prev.next;
prev.next = curr;
curr = curr.next;
}
}
return dummy.next;
}
}