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.
Solution1：Iterative Two pointers "复写" (连接不重复的)
类似83题Solution2:
屏幕快照 2017-09-11 下午3.39.59.png
http://www.jianshu.com/p/ddeed81dc376
Time Complexity: O(N) Space Complexity: O(1)
Solution2：Recursive 先序 写法
思路：递归。先序处理当前，再递归
和第83题Solution3_a 思路相同 http://www.jianshu.com/p/ddeed81dc376
Time Complexity: O(N) Space Complexity: O(N) 递归缓存
Solution1 Code：
class Solution1 {
public ListNode deleteDuplicates(ListNode head) {
if(head == null) return null;
ListNode dummy = new ListNode(0);
dummy.next=head;
ListNode prev = dummy;
ListNode cur = head;
while(cur != null) {
//cur: skip the duplicates and find the next unique one
while(cur.next != null && cur.val == cur.next.val){
cur = cur.next;
// ListNode save_next = cur.next;// [for fully deletion]
// cur.next = null;
// cur = save_next;
}
if(cur != prev.next) { // there is duplicates, link cur.next
prev.next = cur.next;
}
else { // if no skipping, that is a unique one. Then continue
prev = prev.next;
}
cur = cur.next;
}
return dummy.next;
}
}
Solution2 Code：
class Solution2 {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
if (head.val == head.next.val) {
while (head.next != null && head.val == head.next.val) {
head = head.next;
}
return deleteDuplicates(head.next);
} else {
head.next = deleteDuplicates(head.next);
}
return head;
}
}
