83.Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

给定一个有序数组，删除其中所有重复的元素，使每个元素只出现一次~

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

 

高票答案

wen587sort

 采用了递归的方法~

public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null)return head;
        head.next = deleteDuplicates(head.next);
        return head.val == head.next.val ? head.next : head;
//A ？ B ：C (如果A为真执行B否则执行C),若head.val==head.next.vall,返回head.next舍弃head；否则返回head；
}

不过这个答案的下面有评论：
 I highly doubt if we should use recursion in solving linked list problems. We use it for tree because its stack space is O(logn), where n is the number of nodes. But it’s O(n) space required for linked list, which is very likely to be stack overflow. Point me out if you hold a different opinion.
翻译下：我高度怀疑在链表类问题中是否有使用递归的必要。我们在树中使用是因为树所需的栈空间为O(logn)，n为节点数目；而对于链表来说，需要的栈空间为O(n)，非常容易栈溢出。

我的方法

public ListNode deleteDuplicates(ListNode head) {
if(head==null)
return null;
ListNode nowNode = head;
while(true){
while (nowNode.next != null && nowNode.next.val == nowNode.val)
if (nowNode.next.next != null)
nowNode.next = nowNode.next.next;
else
nowNode.next=null;
if(nowNode.next!=null)
nowNode=nowNode.next;
else
return head;
}
}