[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 条评论
登录 后参与评论

相关文章

来自专栏King_3的技术专栏

leetcode-836-Rectangle Overlap

1724
来自专栏coding...

C语言基础 - 实现单向链表

1013
来自专栏LeetCode

LeetCode SingleNumber I,II,III

Given a non-empty array of integers, every element appears twice except for one....

1010
来自专栏决胜机器学习

PHP数据结构(九) ——图的定义、存储与两种方式遍历

PHP数据结构(九)——图的定义、存储与两种方式遍历 (原创内容,转载请注明来源,谢谢) 一、定义和术语 1、不同于线性结构和树,图是任意两个...

4747
来自专栏赵俊的Java专栏

在O(1)时间复杂度删除链表节点

1213
来自专栏LeetCode

LeetCode 203 & 237. Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, giv...

1110
来自专栏Phoenix的Android之旅

Java中的四舍五入

大概在小学的时候我们就学过四舍五入, 不过在编程语言中这个概念跟我们所熟悉的算法有点出入。 如果面试中考察你对Math.round()的用法,不知道能不能准确答...

852
来自专栏赵俊的Java专栏

排序链表转换为二分查找树

1795
来自专栏数据库

渗透测试中常用的SQL命令基础指南

作为渗透测试人员,仅仅利用漏洞攻击目标然后获得一个Shell是远远不够的。尽管拿到Shell是一件很好的事情(毕竟这是我们渗透测试中非常重要的一部分),但是对客...

3218
来自专栏康怀帅的专栏

MySQL 函数

函数相关内容。 字符函数 字符连接 CONCAT('a','b') 使用指定分隔符进行字符连接 CONCAT_WS('-','a','b') 数字格式化 FOR...

2714

扫码关注云+社区