欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

83.Remove Duplicates from Sorted List

程序员文章站 2024-03-22 14:56:22
...

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.

 

高票答案

 采用了递归的方法~

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;
}
}