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.
Example:
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
Solution:
Iterate through the linked list:
- compare the next node with current node
- if they have same value, run a while loop to delete all nodes from current and all nodes with the same value.
- otherwise, move to n ext node
Code:
/**
* Definition for ListNode
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param ListNode head is the head of the linked list
* @return: ListNode head of the linked list
*/
public static ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
ListNode curt = head;
while (curt != null) {
int dupValue = curt.val;
if (curt.next != null && curt.next.val == dupValue) {
while (curt != null && curt.val == dupValue) {
curt = curt.next;
}
prev.next = curt;
} else {
prev = curt;
curt = curt.next;
}
}
return dummy.next;
}
}