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

相关文章

来自专栏用户2442861的专栏

轻松搞定面试中的链表题目

版权所有,转载请注明出处,谢谢! http://blog.csdn.net/walkinginthewind/article/details/7393134...

722
来自专栏数据魔术师

数据结构-线性表|顺序表|链表(下)

1 1 1 哈喽。各位小伙伴好久不见,热心的小编赶在开学季又来给大家送上满满的干货了。祝大家开心快乐! 继上两次咱们聊了顺序表、单链表、静态链表等知识。那么热爱...

2557
来自专栏C/C++基础

合并两个有序链表

已知两个链表head1和head2各自有序,请把它们合并成一个链表依然有序。结果链表要包含head1和head2的所有节点,即使节点值相同。

852
来自专栏猿人谷

单链表反转的分析及实现

我先画一个单链表,这个单链表有4个元素。我的思路就是,每次把第二个元素提到最前面来。比如下面是第一次交换,我们先让头结点的next域指向结点a2,再让结点a1...

48710
来自专栏java学习

来测试一下你对数据结构中的栈和队列的了解有多少?

选择题 1.向一个栈顶指针为top的链栈中插入一个结点s,执行( )。 A.top.next=s; B.s.next=top.next ;top.next=s;...

5199
来自专栏算法与数据结构

数据结构 重点详解

线性数据结构 线性表-顺序表 代码实现: #include <bits/stdc++.h> #define TRUE 1 #define FALSE 0...

2176
来自专栏calmound

Insertion Sort List

家里网实在太烂了,弄得我都不想上网,每次打开oj特别慢,提交题目等刷出来更慢。对于这题感觉脑子不好用啊,写的好繁琐。不过所幸最终脑子还是转过乐弯。。。就是指针n...

3158
来自专栏我是东东强

数据结构之栈与队列(优先队列/堆)

栈与队列是两种重要的特殊线性表,从结构上讲,两者都是线性表,但从操作上讲,两者支持的基本操作却只是线性表操作的子集,是操作受限制的线性表。栈与队列两者最大的区别...

822
来自专栏张俊红

数据结构-栈和队列

我们把类似于弹夹那种先进后出的数据结构称为栈,栈是限定仅在表尾进行插入和删除操作的线性表,我们把允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何数据元素的...

902
来自专栏专知

关关的刷题日记98 – Leetcode 106. Construct Binary Tree from Inorder

关关的刷题日记98 – Leetcode 106. Construct Binary Tree from Inorder and Postorder Trave...

3406

扫码关注云+社区