前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每天一道剑指offer-删除链表中重复的结点

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

作者头像
乔戈里
发布2019-03-04 10:51:55
4730
发布2019-03-04 10:51:55
举报
文章被收录于专栏:Java那些事

删除链表中重复的结点

题目描述

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

代码语言:javascript
复制
public ListNode deleteDuplication(ListNode pHead){

}
解析

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

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

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

代码语言:javascript
复制
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

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-02-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员乔戈里 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 删除链表中重复的结点
    • 题目描述
      • 解析
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档