[LeetCode] 82. Remove Duplicates from Sorted List II

【原题】 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.

【解释】 给定一个已经排序的单链表,要求删除链表当中所有的重复结点。 【思路】 这里最坑的是leetcode上链表并不带有头结点的链表,结果导致要将待删除结点分为头结点和非头结点的判断,增加了很多不必要的操作。 要是有头结点世界该多美好啊! 还傻傻地做了很多判断,看到My accepted Java code的解法,有如醍醐灌顶,没有头结点不会自己造一个??? Mark一下。

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null) return head;
        ListNode fakeHead=new ListNode(0);//新建一个头结点
        fakeHead.next=head;
        ListNode pre=fakeHead, 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;
    }
}

除此之外可以使用递归的解法。 参考My Recursive Java Solution

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
            if(head==null) return head;
        if(head.next!=null&&head.next.val==head.val){
                while(head.next!=null&&head.next.val==head.val)//循环直到找到一个不重复的node
                    head=head.next;

            return deleteDuplicates(head.next);
        }
        else head.next=deleteDuplicates(head.next);//相邻无重复
        return head;
        }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏跟着阿笨一起玩NET

c# 使用timer定时器操作,上次定时到了以后,下次还未执行完怎么处理

------解决方案-------------------------------------------------------- 开始的时候,禁用定时器,你...

3091
来自专栏闵开慧

eclipse中运行hbase时显示Connection refused: no furthe...

java.net.ConnectException: Connection refused: no further information at ...

5487
来自专栏Golang语言社区

Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1192
来自专栏c#开发者

Clean up your BizTalk databases

Here are a few scripts / stored procedures that most of the Biztalk newbies woul...

3454
来自专栏IT杂记

Storm客户端提交任务失败原因分析

2710
来自专栏小鹏的专栏

ubuntu下C++如何调用python程序,gdb调试C++代码

Linux下gdb调试C++代码:http://jingyan.baidu.com/article/acf728fd464984f8e410a369.html ...

2809
来自专栏生信技能树

基因名变化太快,比如PAM50

当然准备把这些基因跟ensembl数据库的ID对应的时候我发现少了3个,然后我搜索发现它们的symbol其实被修改了,可以说变化比较快啦,才几年时间,3 of ...

1092
来自专栏码匠的流水账

聊聊spring cloud的HystrixAutoConfiguration

本文主要研究一下spring cloud的HystrixAutoConfiguration

1162
来自专栏余生开发

echarts太阳分布图-饼图来回穿梭

var dom = document.getElementById("container");

1442
来自专栏FD的专栏

Effective Testing with RSpec 3 (英文版)(序言)

Early praise for Effective Testing with RSpec 3

1864

扫码关注云+社区