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.
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
分析:
用if判断valToDelete还是prev = prev.next,然后用while删除
很难写对,因为所有的条件必须是
while (prev.next != null && prev.next.next != null)
这是因为双层while嵌套导致的...
解法:
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) {
// write your code here
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy;
while (prev.next != null && prev.next.next != null) {
if (prev.next.val == prev.next.next.val) {
int valToDelete = prev.next.val;
while (prev.next != null && prev.next.val == valToDelete) {
prev.next = prev.next.next;
}
} else {
prev = prev.next;
}
}
return dummy.next;
}
}