专栏首页Java那些事每天一道剑指offer-删除链表中重复的结点

每天一道剑指offer-删除链表中重复的结点

删除链表中重复的结点

题目描述

在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5

public ListNode deleteDuplication(ListNode pHead){

}

解析

此题处理起来棘手的有两个地方:

  1. 如果某个结点的后继结点与其重复,那么删除该结点的一串连续重复的结点之后如何删除该结点本身,这就要求我们需要保留当前遍历结点的前驱指针。 但是如果从头结点开始就出现一连串的重复呢?我们又如何删除删除头结点,因此我们需要新建一个辅助结点作为头结点的前驱结点。
  2. 在遍历过程中如何区分当前结点是不重复的结点,还是在删除了它的若干后继结点之后最后也要删除它本身的重复结点?这就需要我们使用一个布尔变量记录是否开启了删除模式( deleteMode

经过上述两步分析,我们终于可以安心遍历结点了:

public ListNode deleteDuplication(ListNode pHead){
    if(pHead == null){
        return null;
    }
    ListNode node = new ListNode(Integer.MIN_VALUE);
    node.next = pHead;
    ListNode pre = node, p = pHead;
    boolean deletedMode = false;
    while(p != null){
        if(p.next != null && p.next.val == p.val){
            p.next = p.next.next;
            deletedMode = true;
        }else if(deletedMode){
            pre.next = p.next;
            p = pre.next;
            deletedMode = false;
        }else{
            pre = p;
            p = p.next;
        }
    }

    return node.next;
}

出自:http://www.zhenganwen.top

已获授权

END

本文分享自微信公众号 - 程序员乔戈里(CXYqiaogeli)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-02-11

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 恕我直言,有了这款IDEA插件,你可能只需要写30%的代码...

    EasyCode是基于IntelliJ IDEA开发的代码生成插件,支持自定义任意模板(Java,html,js,xml)。只要是与数据库相关的代码都可以通过自...

    乔戈里
  • 每天一道剑指offer-链表中环的入口结点

    乔戈里
  • 每天一道leetcode142-寻找链表中环的入口

    乔戈里
  • 「优质题解」出圈

    https://www.dotcpp.com/oj/problem1160.html

    编程范 源代码公司
  • 编程小白 | 每日一练(42)

    这道理放在编程上也一并受用。在编程方面有着天赋异禀的人毕竟是少数,我们大多数人想要从编程小白进阶到高手,需要经历的是日积月累的学习,那么如何学习呢?当然是每天都...

    C语言入门到精通
  • 数据结构 | 每日一练(73)

    ——老子

    C语言入门到精通
  • 数据结构 第4讲 单链表

    链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻,那么怎么表示逻辑上的相邻关系呢?可以给每个元素附加一个指针域,指向下一个元素的存储位...

    rainchxy
  • 数据结构 | 每日一练(21)

    ——老子

    C语言入门到精通
  • HashMap为什么存在线程不安全呢?

    本文主要探讨下HashMap 在多线程环境下容易出现哪些问题,深层次理解其中的HashMap。

    田维常
  • 算法-O(1)时间删除链表的指定结点

    题目:给定一个链表的头指针和一个结点的指针,定义一个函数在O(1)时间删除该结点。链表结点与函数的定义如下: struct ListNode { int v...

    chaibubble

扫码关注云+社区

领取腾讯云代金券