剑指Offer（五十六）：删除链表中重复的结点

2018年1月25日09:20:51 24 8,842 °C

摘要

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台：牛客网

书籍下载：共享资源

二、题目

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

1、思路

删除重复结点，只需要记录当前结点前的最晚访问过的不重复结点pPre、当前结点pCur、指向当前结点后面的结点pNext的三个指针即可。如果当前节点和它后面的几个结点数值相同，那么这些结点都要被剔除，然后更新pPre和pCur；如果不相同，则直接更新pPre和pCur。

需要考虑的是，如果第一个结点是重复结点我们该怎么办？这里我们分别处理一下就好，如果第一个结点是重复结点，那么就把头指针pHead也更新一下。

2、代码

C++：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if(pHead == NULL){
            return NULL;
        }
        // 指向当前结点前最晚访问过的不重复结点
        ListNode* pPre = NULL;
        // 指向当前处理的结点
        ListNode* pCur = pHead;
        // 指向当前结点后面的结点
        ListNode* pNext = NULL;
        
        while(pCur != NULL){
            // 如果当前结点与下一个结点相同
            if(pCur->next != NULL && pCur->val == pCur->next->val){
                pNext = pCur->next;
                // 找到不重复的最后一个结点位置
                while(pNext->next != NULL && pNext->next->val == pCur->val){
                    pNext = pNext->next;
                }
                // 如果pCur指向链表中第一个元素，pCur -> ... -> pNext ->... 
                // 要删除pCur到pNext, 将指向链表第一个元素的指针pHead指向pNext->next。
                if(pCur == pHead){
                    pHead = pNext->next;
                }
                // 如果pCur不指向链表中第一个元素，pPre -> pCur ->...->pNext ->... 
                // 要删除pCur到pNext，即pPre->next = pNext->next
                else{
                    pPre->next = pNext->next;
                }
                // 向前移动
                pCur = pNext->next;
            }
            // 如果当前结点与下一个结点不相同
            else{
                pPre = pCur;
                pCur = pCur->next;
            }
        }
        return pHead;
    }
};

struct ListNode {

int val;

struct ListNode *next;

ListNode(int x) :

val(x), next(NULL) {

}

};

class Solution {

public:

ListNode* deleteDuplication(ListNode* pHead)

{

if(pHead == NULL){

return NULL;

}

// 指向当前结点前最晚访问过的不重复结点

ListNode* pPre = NULL;

// 指向当前处理的结点

ListNode* pCur = pHead;

// 指向当前结点后面的结点

ListNode* pNext = NULL;

while(pCur != NULL){

// 如果当前结点与下一个结点相同

if(pCur->next != NULL && pCur->val == pCur->next->val){

pNext = pCur->next;

// 找到不重复的最后一个结点位置

while(pNext->next != NULL && pNext->next->val == pCur->val){

pNext = pNext->next;

}

// 如果pCur指向链表中第一个元素，pCur -> ... -> pNext ->...

// 要删除pCur到pNext, 将指向链表第一个元素的指针pHead指向pNext->next。

if(pCur == pHead){

pHead = pNext->next;

}

// 如果pCur不指向链表中第一个元素，pPre -> pCur ->...->pNext ->...

// 要删除pCur到pNext，即pPre->next = pNext->next

else{

pPre->next = pNext->next;

}

// 向前移动

pCur = pNext->next;

}

// 如果当前结点与下一个结点不相同

else{

pPre = pCur;

pCur = pCur->next;

}

return pHead;

}

};

Python：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        pPre = None
        pCur = pHead
        pNext = None
        while pCur != None:
            if pCur.next != None and pCur.val == pCur.next.val:
                pNext = pCur.next
                while pNext.next != None and pNext.next.val == pCur.val:
                    pNext = pNext.next
                if pCur == pHead:
                    pHead = pNext.next
                else:
                    pPre.next = pNext.next
                pCur = pNext.next
            else:
                pPre = pCur
                pCur = pCur.next
        return pHead

# -*- coding:utf-8 -*-

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

def deleteDuplication(self, pHead):

# write code here

pPre = None

pCur = pHead

pNext = None

while pCur != None:

if pCur.next != None and pCur.val == pCur.next.val:

pNext = pCur.next

while pNext.next != None and pNext.next.val == pCur.val:

pNext = pNext.next

if pCur == pHead:

pHead = pNext.next

else:

pPre.next = pNext.next

pCur = pNext.next

else:

pPre = pCur

pCur = pCur.next

return pHead

微信公众号

分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。

版权声明：本站原创文章，于2018年1月25日09:20:51，由 Jack Cui 发表，共 416 字。
转载请注明：剑指Offer（五十六）：删除链表中重复的结点 | Jack Cui

发表评论取消回复

目前评论：24 其中：访客 15 博主 9

哈苏地方 上海市上海理工大学 4
回复 2018年4月5日下午3:53 沙发
666
- Jack Cui Admin 辽宁省沈阳市联通GSM/WCDMA/LTE共用出口
  回复 2018年4月5日下午7:03 1层
  @哈苏地方感谢支持
发文局域网对方和您在同一内部网 4
回复 2018年7月18日下午4:16 板凳
pPre用来改变实际指针
- Jack Cui Admin 北京市百度网讯科技联通节点
  回复 2018年7月18日下午5:29 1层
  @发文嗯~
- selami 黑龙江省移动 0
  回复 2020年10月17日下午8:08 1层
  @发文为啥pPre是用来改变实际指针的，而pCur和pNext没有这种功能呢，看了好久就卡在这里，望指点！！！！
Lucas 江苏省苏州市电信 2
回复 2019年3月14日上午11:43 地板
请问重复的结点不保留，不是还需要delete吗
- Jack Cui Admin 北京市百度网讯科技联通节点
  回复 2019年3月14日下午1:40 1层
  @Lucas 链表删除节点，就是让next指针绕过删除的节点。
Jason 北京市联通 0
回复 2019年5月26日下午6:14 4楼
想问下，因为生成了三个新的指针，这种空间复杂度是O(1)还是O(n)?
- Jack Cui Admin 北京市百度网讯科技联通节点
  回复 2019年5月27日上午9:28 1层
  @Jason O(1)哈～
opti 山东省济南市山东大学齐鲁软件学院 1
回复 2019年5月31日下午6:50 5楼
真好
opti 山东省济南市山东大学齐鲁软件学院 1
回复 2019年5月31日下午6:52 6楼
话说没有delete，那节点空间岂不是浪费了
- Jack Cui Admin 北京市百度网讯科技联通节点
  回复 2019年6月3日上午9:44 1层
  @opti 有新值来了会覆盖的～
尖沙咀段坤 北京市电信 1
回复 2019年8月5日下午4:57 7楼
楼主你好，C++版本中【20】ListNode* pCur = pHead; 与后面【34】if(pCur == pHead) 是否矛盾呢？
- Jack Cui Admin 北京市百度网讯科技联通节点
  回复 2019年8月5日下午6:36 1层
  @尖沙咀段坤不矛盾，这个就是为了处理头结点的。
  - 尖沙咀段坤 北京市电信 1
    回复 2019年8月5日下午7:08 2层
    @Jack Cui 感谢回复！我的意思是前面一句已经设置 pCur与pHead相等，那后面 if 语句肯定成立呀，那else语句是不是永远不会执行呢，不知这样理解有没有问题哈？谢谢！
    - Jack Cui Admin 北京市百度网讯科技联通节点
      回复 2019年8月6日下午12:48 3层
      @尖沙咀段坤 pCur = pNext->next，pCur移动的啊。
晓晓晓满 湖北省武汉市华中科技大学东校区 1
回复 2019年8月7日下午4:37 8楼
你好，博主，因为我基础比较差，所以问一个比较愚蠢的问题，哈哈，希望不要被嫌弃。python版本的答案里面的pPre=None，这个None是空值还是空的链表结点呢？为什么后边它可以直接给它的pPre.next赋值呢？
- Jack Cui Admin 北京市百度网讯科技联通节点
  回复 2019年8月7日下午8:00 1层
  @晓晓晓满 pPre和pNext为None，就是空值。一个记录前节点，一个记录后节点。next识链表的结构里定义的，指向的是下一个节点的地址。
  - 晓晓晓满 湖北省武汉市华中科技大学东校区 1
    回复 2019年8月7日下午9:19 2层
    @Jack Cui 感谢回答。可能是我没表达清楚，我的意思是为什么 None不就代表空值吗，它为什么可以使用链表结构定义里的next呢？还是说这个None也是链表的结构定义的None呀？
    - Jack Cui Admin 北京市百度网讯科技联通节点
      回复 2019年8月8日上午9:42 3层
      @晓晓晓满这是初始化为None，后面赋新指了，指向了链表节点后，自然就可以用了啊。
    - 一书一世界 黑龙江省哈尔滨市联通 2
      回复 2020年8月3日上午11:57 3层
      @晓晓晓满我第一遍看时也有疑问，但是当你分析程序流程的时候发现，python中在执行20行之前，23行肯定肯定肯定被执行过了，所以执行20行也就不是问题了。程序的逻辑还是有点绕。
小占同学 IANA 保留地址 1
回复 2019年8月28日下午8:54 9楼
您好，当测试用例为1->1>1时，
if(pCur == pHead){
pHead = pNext->next;
}
中的pNext->next不就为NULL了么？那方法deleteDuplication最后返回的pHead不也为NULL吗？请指教，谢谢
- 一书一世界 黑龙江省哈尔滨市联通 2
  回复 2020年8月3日上午11:42 1层
  @小占同学删除该链表中重复的结点，指的是重复的结点不保留。分析代码时候潜意识中想法总是认为是删除重复后保留一个即可，导致看代码很混乱。
一书一世界 黑龙江省哈尔滨市联通 2
回复 2020年8月3日上午11:39 10楼
本题要认真读题，删除该链表中重复的结点，指的是重复的结点不保留。分析代码时候潜意识中想法总是认为是删除重复后保留一个即可，导致看代码很混乱。
疑问：链表只是单纯删除重复节点，链表中的每个节点都是new出来的。链表删除节点，就是让next指针绕过删除的节点没错，但是被删除的节点不delete，以后即使想用这个节点找都找不到啊，怎么不需要delete呢？