Problem
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.
My Solution
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode h = new ListNode(Integer.MIN_VALUE);
h.next = head;
ListNode current = head;
ListNode t = h;
boolean flag = false;
while (current != null && current.next != null) {
if (current.next.val == current.val) {
current = current.next;
t.next = current;
flag = true;
} else if (flag == true) {
current = current.next;
t.next = current;
if (current.next != null && current.next.val != current.val) {
t = t.next;
current = current.next;
}
flag = false;
} else if (flag == false) {
current = current.next;
t = t.next;
}
}
if (flag == true) {
current = current.next;
t.next = current;
t = t.next;
} else if (flag == false && current != null) {
current = current.next;
t = t.next;
}
return h.next;
}
}
Great Solution
public ListNode deleteDuplicates(ListNode head) {
if(head==null) return null;
ListNode FakeHead=new ListNode(0);
FakeHead.next=head;
ListNode pre=FakeHead;
ListNode cur=head;
while(cur!=null){
while(cur.next!=null&&cur.val==cur.next.val){
cur=cur.next;
}
if(pre.next==cur){
pre=pre.next;
}
else{
pre.next=cur.next;
}
cur=cur.next;
}
return FakeHead.next;
}
