资讯专栏INFORMATION COLUMN

leetcode82. Remove Duplicates from Sorted List II

崔晓明 / 2799人阅读

摘要:题目要求翻译将链表中重复的元素全部删除,返回新的头结点。相比于,这里将重复的元素全部删除。除此以外,我们还需要知道重复元素的前一个值和重复元素的最后一个值。如果存在重复值,则跳过重复值后,前节点不变,否则前节点跟随后节点同时向后移动。

题目要求
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.

翻译:将链表中重复的元素全部删除,返回新的头结点。

相比于Remove Duplicates from Sorted List I,这里将重复的元素全部删除。
想要了解Remove Duplicates from Sorted List I,请参考我的这篇博客

思路和代码

这里,我们首先需要一个伪头节点指向当前的头节点,以确保我们最后能够找到结果集的头节点。除此以外,我们还需要知道重复元素的前一个值和重复元素的最后一个值。
举个例子:如果数组元素为[1,2,2,3],那么我们需要知道1这个节点和3这个节点的位置,并将1的下一个节点指向3。特殊情况,如[1,1,2,2],这是我们就可以将伪头结点作为我们的前节点,并将2作为我们的后节点。如果存在重复值,则跳过重复值后,前节点不变,否则前节点跟随后节点同时向后移动。代码如下:

    public ListNode deleteDuplicates(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode start = new ListNode(0);
        start.next = head;
        ListNode prevNode = start;
        ListNode current = head;
        while(current != null){
            if(current.next != null && current.val == current.next.val){
                do{
                    current = current.next;
                }while(current.next != null && current.val == current.next.val);
                prevNode.next = current.next;
            }else{
                prevNode = current;
            }
            current = current.next;
        }
        return start.next;
    }
    
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x;}
    }


想要了解更多开发技术,面试教程以及互联网公司内推,欢迎关注我的微信公众号!将会不定期的发放福利哦~

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/67231.html

相关文章

  • 82. Remove Duplicates from Sorted List II

    Given a sorted linked list, delete all nodes that have duplicatenumbers, leaving only distinct numbers from the original list. https://leetcode.com/problems... # Definition for singly-linked list. # c...

    zhou_you 评论0 收藏0
  • leetcode80. Remove Duplicates from Sorted Array II

    摘要:思路与代码其实在这里我们仍然延续中的思路。在遇到非重复值以及非多余的重复值时,将数值移动到当前记录的下标上。保证该下标前的值均为满足题目条件的值。第一次我使用了来记录某个值出现的次数。 题目要求 Follow up for Remove Duplicates: What if duplicates are allowed at most twice? For example, Giv...

    CoderDock 评论0 收藏0
  • leetcode部分题目答案之JavaScript版

    摘要:自己没事刷的一些的题目,若有更好的解法,希望能够一起探讨项目地址 自己没事刷的一些LeetCode的题目,若有更好的解法,希望能够一起探讨 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

    alphahans 评论0 收藏0
  • LeetCode 攻略 - 2019 年 7 月上半月汇总(55 题攻略)

    摘要:微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容,进行补充,并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目录 不...

    warmcheng 评论0 收藏0
  • [LintCode/LeetCode] Remove Duplicates from Sorted

    摘要:思路原数组长度为,则返回原数组长度不为,则至少有个元素。将所有不重复的数值赋给,而当和相等时,不做处理。最后返回的就是不同元素的个数,也是新数组的长度。只有在时,才对赋值。注意,每次初始化的时候要分两种情况,这就意味着从的时候开始遍历。 Remove Duplicates from Sorted Array I Problem Given a sorted array, remove ...

    WalkerXu 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<