Question
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.
Stats
| Frequency | 3 |
| Difficulty | 3 |
| Adjusted Difficulty | 2 |
| Time to use | ---------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
This is a very important question. Solution is a little tricky with boundary cases that need consider.
My code works, but there is an extremely good solution posted below.
Code
First, my code
public ListNode deleteDuplicates(ListNode head) {
ListNode preHead = new ListNode(0);
preHead.next = head;
ListNode left = preHead, right = head;
while (right != null) {
if (right.next == null || right.val != right.next.val) {
// next is differnet from previous
left = right;
right = right.next;
}
else {
// next is same as previous
while (right.next != null && right.val == right.next.val)
right = right.next;
left.next = right.next;
right = right.next;
}
}
return preHead.next;
}
Second, a great solution from this blog.
public ListNode deleteDuplicates(ListNode head) {
if(head == null) return head;
ListNode helper = new ListNode(0);
helper.next = head;
ListNode pre = helper, cur = head;
while(cur!=null)
{
while(cur.next!=null && pre.next.val==cur.next.val)
cur = cur.next;
if (pre.next == cur)
pre = pre.next;
else
pre.next = cur.next;
cur = cur.next;
}
return helper.next;
}