首页 > 试题广场 >

删除链表中重复的结点

[编程题]删除链表中重复的结点

热度指数：808844 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围：链表长度满足 $0 \le n \le 1000 \$ ，链表中的值满足 $1 \le val \le 1000 \$

进阶：空间复杂度 $O(n)\$ ，时间复杂度 $O(n) \$

例如输入{1,2,3,3,4,4,5}时，对应的输出为{1,2,5}，对应的输入输出链表如下图所示：

示例1

输入

{1,2,3,3,4,4,5}

输出

{1,2,5}

示例2

输入

{1,1,1,8}

输出

{8}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

Python

zxlly要offer

# -*- coding:utf-8 -*-
'''
题目：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 
例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
'''
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        if pHead == None or pHead.next == None:
            return pHead
        new_head = ListNode(-1)
        new_head.next = pHead
        pre = new_head
        p = pHead
        nex = None
        while p != None and p.next != None:
            nex = p.next
            if p.val == nex.val:
                while nex != None and nex.val == p.val:
                    nex = nex.next
                pre.next = nex
                p = nex
            else:
                pre = p
                p = p.next
        return new_head.next

编辑于 2018-05-19 15:22:25 回复(9)

Python

TimeMac

class Solution:
    def deleteDuplication(self, pHead):
        if not pHead or not pHead.next:
            return pHead
        if pHead.val == pHead.next.val:
            temp = pHead.next
            while temp and temp.val == pHead.val:
                temp = temp.next
            return self.deleteDuplication(temp)
        else:
            pHead.next = self.deleteDuplication(pHead.next)
            return pHead

编辑于 2018-10-21 22:45:43 回复(1)

披萨大叔

思考：化繁为简，先找到第一个符合的结点，以后递归。

 public ListNode deleteDuplication(ListNode pHead){
		if(pHead == null){
            return null;
        }        
        if(pHead.next == null){
            return pHead;
        }
        //两个循环，用来应付“1-1-2-2-3-3-4-5…”格式的连续重复结点
        while(pHead != null && pHead.next != null && pHead.val == pHead.next.val){
            while(pHead != null && pHead.next != null && pHead.val == pHead.next.val){
                pHead = pHead.next;
            }
             pHead = pHead.next;
        }
        if(pHead!=null ){
            pHead.next = deleteDuplication(pHead.next);
        }
        return pHead;
    }

发表于 2016-07-17 16:13:58 回复(4)

跪求offer养家糊口

/*
*因为需要删除重复的节点，所以需要保留一个待删除节点之前的节点，这里用一个指针pre来
*表示，另外再用一个指针p指向正在遍历的节点。当头节点与后续节点数值相等时，需要特殊
*处理。方法比较简单，就是注意不要出现NULL->next,引起系统报错。
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if (pHead == NULL)
            return NULL;
        ListNode *pre = NULL;
        ListNode *p = pHead;
        int flag = 0;   //判断是否出现重复节点，当flag==1时，当前节点出现重复
        while (p)
        {
            while (p->next && p->val == p->next->val)  //如果节点重复，一直遍历下去
            {
                flag = 1;
                p = p->next;
            }
            if (flag == 0)   //如果当前节点不重复，遍历下一个节点
            {
                pre = p;
            	p = p->next;
            }
            else     //如果当前节点重复，分类处理
            {
                flag = 0;
                if (pre == NULL)   //如果从头结点开始出现重复，重置头结点指针
                {
                    pHead = p->next;
                    p = pHead;
                }
                else              //否则，跳过重复的节点
                {
                    pre->next = p->next;
                	p = pre->next;
                }  
            }
        }
        return pHead;
    }
};

发表于 2017-07-31 11:06:02 回复(1)

Pisces

public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        if(pHead==null)return null;
       	
        ListNode preNode = null;
        ListNode node = pHead;
        while(node!=null){
            ListNode nextNode = node.next;
            boolean needDelete = false;
            if(nextNode!=null&&nextNode.val==node.val){
                needDelete = true;
            }
            if(!needDelete){
                preNode = node;
                node = node.next;
            }
            else{
                int value = node.val;
                ListNode toBeDel = node;
                while(toBeDel!=null&&toBeDel.val == value){
                    nextNode = toBeDel.next;
                    toBeDel = nextNode;
                    if(preNode==null)
                        pHead = nextNode;
                    else
                        preNode.next = nextNode;
                    node = nextNode;
                }
            }
        }
        
        return pHead;
    }
}

发表于 2016-05-05 11:19:26 回复(4)

Java

牛客102377600号

先遍历链表把结点全部保存到map，对重复结点做好标记，再重新遍历链表，将重复结点删除掉。

import java.util.*;

public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
Map<Integer, Boolean> map = new HashMap<>();
ListNode p = pHead;
while (p != null) {
if (map.containsKey(p.val)) {
map.put(p.val, true);
} else {
map.put(p.val, false);
}
p = p.next;
}

while (pHead != null && map.containsKey(pHead.val) && map.get(pHead.val)) {
pHead = pHead.next;
}

ListNode q = pHead;
while (q != null && q.next != null) {
if (map.containsKey(q.next.val) && map.get(q.next.val)) {
q.next = q.next.next;
continue;
}
q = q.next;
}
return pHead;
}
}

发表于 2021-10-12 11:54:46 回复(0)

Python

哄哄2739

单层循环的简单解法

删除链表需要用到多个指针，比如上图中，我们想要删除节点q，只需要把p.next指向r即可。所以我们使用3个指针，p代表前一个节点，q和r是后面两个节点，是每次循环时用来比较的。首先，p保证与q的值不相等，因此只有当我们完成下面的一个数的操作（不论是保留还是删除），才会更新它。比如最简单的情况，q与r不相等，那么我们直接移动指针即可（左图）如果q与r相等呢？这时候我们需要继续往下寻找这个数的最后一个，所以不移动p，只移动q和r，直到q与r不相等时才停止。此时删除这些中间节点。总结一下，我们只需要一直往下遍历q和r，如果他们不等，则有两种情况，一个是p的下一个就是q，那么就没有重复，更新p；如果p的下一个不是q，则说明有重复，这时更新p的next，删除节点。这里还需要注意链表尾部是重复节点的问题，由于我们不知道什么时候会遇到最后一个重复的数，当循环结束时还没有遇到的情况，就无法执行更新p.next了，所以要在最后再进行一次判断，p与q不相连的话则需要删除它们。

class Solution:
    def deleteDuplication(self, pHead):
        head = ListNode(None)
        head.next = pHead

        p = head
        q = pHead

        # 输入为空
        if not q:
            return None
        
        # 循环整个链表
        while q.next:
            # 当 q 不等于 r 时
            if q.val != q.next.val:
                # p 与 q 不相连，说明有重复
                if q != p.next:
                    p.next = q.next
                # p 与 q 相连，不处理，继续移动 p
                else:
                    p = q

            q = q.next

        # 判断链表结尾是重复的问题
        if q != p.next:
            p.next = q.next

        return head.next

发表于 2020-02-16 00:08:56 回复(0)

锦鲤大法

满屏全是递归的算法，分享一个不是用递归，单纯用指针实现的方法：

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
		ListNode* p=pHead;
        if(!p||!p->next) return pHead;
        ListNode* pre=NULL;
        bool check = false;
        while(p){
            while(p->next&&p->val==p->next->val){
                p = p->next;
                check = true;
            }
            if(check){
                if(pre) pre->next = p->next;
                else pHead = p->next;
                check = false;
            }
            else{
                pre = p;
            }
            if(p){
            	p = p->next;
            }
        }
        return pHead;
    }
};

发表于 2017-09-11 22:21:16 回复(0)

Java

Vzer

//Java版递归
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null) return null;
        if (pHead.next == null) return pHead;
        ListNode cur;

        //对重复结点的处理
        if (pHead.val == pHead.next.val) {
            cur = pHead.next.next;
            //遍历到没有重复结点的位置
            while (cur != null && cur.val == pHead.val) {
                cur = cur.next;
            }
            return deleteDuplication(cur);
        }

        //该结点不重复，递归下一个结点
        cur = pHead.next;
        pHead.next = deleteDuplication(cur);
        return pHead;
    }

编辑于 2017-05-09 23:07:47 回复(0)

C/C++

老衲心如止水

class Solution {

public:

ListNode* deleteDuplication(ListNode* pHead)

{

if(pHead==NULL || pHead->next == NULL)

return pHead;

//添加一个哨兵节点

ListNode* pFirst = new ListNode(-1);

pFirst->next = pHead;

ListNode* prev = pFirst;

ListNode* curr = pHead;

while(curr != NULL )

{

while(curr->next != NULL && curr->val == curr->next->val)

{

curr = curr->next;

}

if(prev->next == curr)

{

prev = curr;

curr = curr->next;

}else{

curr = curr->next;

prev->next = curr;

}

return pFirst->next;

}

};

发表于 2016-12-08 14:40:36 回复(2)

周星星_

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if(pHead==0) return 0;

        map<int,int> m;
        ListNode* p=pHead;
        while(p!=0)
        {
            m[p->val]++;
            p=p->next;
        }
        //判断head
        while(m[pHead->val]>1)
        {
            pHead=pHead->next;
            if(pHead==0) return 0;
        }
        ListNode* p1=pHead;
        ListNode* p2=pHead->next;
        while(p2!=0)
        {
            if(m[p2->val]>1)
            {
                p2=p2->next;
                p1->next=p2;
            }
            else
            {
                p2=p2->next;
                p1=p1->next;
            }
        }
        return pHead;
    }
};

编辑于 2016-08-13 12:56:19 回复(2)

neuxs

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
import java.util.HashMap;
public class Solution {
	public ListNode deleteDuplication(ListNode pHead)
	   {
		       if(pHead==null || pHead.next==null)
		           return pHead;
	        ListNode list=new ListNode(-1);
	        ListNode demo=list;
	        ListNode p=pHead;
	        ListNode q=null;        
	        while(p!=null){
	            int value=p.val;
	            q=p;
	            if((q.next!=null) && (value==q.next.val)){
	                while((q.next!=null)&&(value==q.next.val)){
	                    q=q.next;
	                }
	                p=q.next;                
	            }else{
	            	ListNode newnode=new ListNode(p.val);
	                demo.next=newnode;
	                demo=demo.next;    
	                p=p.next;
	            }
	           }
		   return list.next;    
		}
}

发表于 2016-01-13 16:42:07 回复(0)

马客(Mark)

两种实现

typedef ListNode node;
typedef node* pode;
class Solution {
public:
    ListNode* deleteDuplication(ListNode* p){
        node h(0x23333), *q = &h, *tmp;
        int cnt;
        while(p){
            tmp = p; p = p -> next; cnt = 0;
            while(p && p -> val == tmp -> val) p = p -> next, ++cnt;
            if(!cnt) q -> next = tmp, q = tmp;
        }
        q -> next = NULL;
        return h.next;
    }
};

typedef ListNode node;
typedef node* pode;
class Solution {
public:
    ListNode* deleteDuplication(ListNode* p){
        node h(0x23333), *q = &h;
        while(p){
            while(p && p -> next && p -> next -> val == p -> val){
                while(p -> next && p -> next -> val == p -> val) p = p -> next;
                p = p -> next;
            }
            if(!p) break;
            q -> next = p; q = p; p = p -> next;
        }
        q -> next = NULL;
        return h.next;
    }
};

编辑于 2015-09-16 14:42:54 回复(0)

魅影骑士

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
/*
	算法思想：方法一，递归实现。
    public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
		if(pHead == null || pHead.next == null) return pHead;
         
        if(pHead.val != pHead.next.val){
            pHead.next = deleteDuplication(pHead.next);
            return pHead;
        }else{
            int val = pHead.val;
            while(pHead.val == val){
                pHead = pHead.next;
                if(pHead == null) return null;
            }
            return deleteDuplication(pHead);
        }
    }
}
*/
/*
	算法思想：把当前结点的前一个结点（pre）和后面值比当前结点的值要大的结点相连。
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        if(pHead == null || pHead.next == null) return pHead;
        ListNode temp = new ListNode(-1);
        temp.next = pHead;
        ListNode curNode = pHead;
        ListNode pre = temp;
         while(curNode != null && curNode.next != null){
            ListNode next = curNode.next;
            if(curNode.val == next.val){
                while(next != null && curNode.val == next.val){
                    next = next.next;
                }
                pre.next = next;
                curNode = next;
            }else{
                pre = curNode;
                curNode = curNode.next;
            }
        }
        return temp.next;
    }
}

发表于 2017-02-27 09:05:36 回复(1)

Java

浅羊

思路

没什么复杂绕圈的，主要还是考验逻辑和代码能力。

刚开始想在if (pHead.next != null && pHead.val == pHead.next.val)里套一个同样内容的while，但强迫症犯了看到重复部分很不爽，花了点时间写成如下形式，看起来简洁一些，我是看着挺舒服的。

说明：
如果当前结点和下一个重复，则pre.next设空，否则，如果pre.next为空，则跳过当前结点（代表当前结点为同类重复结点的最后一个）.

代码

    public ListNode deleteDuplication(ListNode pHead) {
        ListNode h = new ListNode(0), p = h;
        h.next = pHead;
        while (pHead != null) {
            if (pHead.next != null && pHead.val == pHead.next.val) {
                p.next = null;
            } else if (pHead.next != null && p.next == null) {
                p.next = pHead.next;
            } else {
                p = p.next;
            }
            pHead = pHead.next;
        }
        return h.next;
    }

编辑于 2021-02-03 18:12:05 回复(0)

Java

卡卡ni很帅new

//方法一

public ListNode deleteDuplication(ListNode pHead) {
        if(pHead==null||pHead.next==null) return pHead;
        else {
            //新建一个节点，防止头结点要被删除
            ListNode newHead=new ListNode(-1);
            newHead.next=pHead;
            ListNode pre=newHead;
            ListNode p=pHead;
            ListNode next=null;
            while(p!=null && p.next!=null)
            {
                next=p.next;
                if(p.val==next.val)//如果当前节点的值和下一个节点的值相等
                {
                    while(next!=null && next.val==p.val)//向后重复查找
                        next=next.next;
                    pre.next=next;//指针赋值，就相当于删除
                    p=next;
                }
                else{ //如果当前节点和下一个节点值不等，则向后移动一位
                    pre=p;
                    p=p.next;
                }
            }
            return newHead.next;//返回头结点的下一个节点
        }
    }

发表于 2019-09-12 14:25:07 回复(0)

Python

刀轻城_algo

# 思路简单版，为了便于处理头节点，手动增加虚拟首结点，分别设置4个指针
# anchor：标志链接位置，初始化为虚拟首结点
# former：标志待判断节点的直接前驱，初始化为虚拟首结点
# x：标志待判断节点本身，初始化为头节点
# latter：标志待判断节点的直接后继，初始化为头节点后继
# 根据题意，只有某节点与其直接前驱和直接后继都不相同时，才保留
# latter到链表结尾，或者整个链表为空时为退化情况

def deleteDuplication(self, pHead):
    # write code here
    if not pHead: # 如果链表为空
        return None
    Head = ListNode(None) # 虚拟首结点
    Head.next = pHead
    anchor, former, x, latter = Head, Head, Head.next, Head.next.next # 初始化
    while(latter): # 当遍历节点都不是空（都有值）的时候
        if former.val != x.val and x.val != latter.val: # 如果x为一个不重复的节点，则链入返回的链上
            anchor.next = x
            anchor = anchor.next
        former, x, latter = x, latter, latter.next # 指针向后移动
    if former.val == x.val: # 最后一个节点，如果重复就不要，否则要
        anchor.next = None
    else:
        anchor.next = x
    return Head.next # 去掉虚拟首结点，返回

发表于 2019-08-10 10:32:14 回复(1)

字节跳动内推小天才

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        ListNode newHead = new ListNode(-1);
        newHead.next = pHead;
        ListNode pre = newHead;
        ListNode node = pHead;
        while(node!=null&&node.next!=null){
            if(node.val==node.next.val){
                while(node!=null&&node.next!=null&&node.val==node.next.val){
                    node = node.next;
                }
                pre.next = node.next; 
                node = node.next;
            }
            else{
                pre = node;
                node = node.next;
            }          
        }
        return newHead.next;
    }
}

发表于 2019-04-11 11:10:53 回复(0)

Java

Nobody_Zheng

/**

@author zhengyanan

@time 21:52

@description

version_3:

核心思路：

1.先给原链表添加一个头结点方便处理；

2.使用3个指针，一个指向前一个节点last，一个指向当前节点p，一个指向下一个节点p->next。

3.当当前节点跟后一个节点相等时，不断往后遍历，找到第一个不等于当前节点的节点；然后用

last 指向它；当当前节点跟后一个不相等时，将last 后移指向p，p后移一位

    public ListNode deleteDuplication(ListNode pHead){
        ListNode first = new ListNode(Integer.MIN_VALUE),last;
        first.next = pHead;
        last = first;
        while (pHead != null && pHead.next != null) {
            if (pHead.val == pHead.next.val) {
                int val = pHead.val;
                while (pHead!= null && pHead.val == val) pHead = pHead.next;
                last.next = pHead;
            }
            else {
                last = pHead;
                pHead = pHead.next;
            }
        }
        return first.next;
    }

/**

@author zhengyanan

@time 21:33

@description

version_2:

核心思路：

1.基本同version_1，不过借用了容器类，简洁了代码。

运行时间：33ms

占用内存：629k

//    public ListNode deleteDuplication(ListNode pHead){
//        LinkedList<ListNode> result = new LinkedList<ListNode>();
//        result.addLast(new ListNode(Integer.MIN_VALUE));
//        boolean isRepeated = false;
//        while (pHead != null){
//            if (result.getLast().val == pHead.val){
//               isRepeated = true;
//            }
//            else {
//                if (isRepeated){
//                    result.removeLast();
//                    isRepeated = false;
//                }
//                result.addLast(pHead);
//            }
//            pHead = pHead.next;
//        }
//        if (isRepeated) result.removeLast();
//
//        if (result.size() == 1) return null;
//
//        for (int i = 0; i < result.size() - 1; i++) {
//            result.get(i).next = result.get(i+1);
//        }
//        result.get(result.size() - 1).next = null;
//
//        return result.get(0).next;
//    }

/**

@author zhengyanan

@time 21:10

@description

version_1:

核心思路：

1.先给原链表添加一个头结点；

2.循环一遍，每当访问当前节点时，判断其后紧跟的几个是否跟它相等，相等就删除，

并把当前访问节点的值标记为MAX；

3.在循环一遍，去掉值为MAX的；

4.返回头结点的next即可。

//    public ListNode deleteDuplication(ListNode pHead){
//        ListNode tHead = new ListNode(Integer.MIN_VALUE),t;
//        boolean isRepeated;
//        tHead.next = pHead;
//
//        pHead = tHead;
//        while (pHead != null){
//            isRepeated = false;
//
//            t = pHead.next;
//            if (t == null)  break;
//
//            while (t.val == pHead.val){
//                isRepeated = true;
//                t = t.next;
//                if (t == null){
//                    pHead.next = null;
//                    break;
//                }
//            }
//
//            pHead.next  = t;
//            if (isRepeated) pHead.val = Integer.MAX_VALUE;
//            pHead = pHead.next;
//        }
//
//        pHead = tHead;
//        while (pHead != null){
//            if (pHead.next == null) break;
//            else if (pHead.next.val == Integer.MAX_VALUE){
//                pHead.next = pHead.next.next;
//            }else {
//                pHead = pHead.next;
//            }
//        }
//
//        return tHead.next;
//    }

发表于 2017-03-05 22:17:28 回复(0)

搬一块叫CV的砖

/*
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* pPreNode = NULL;
        ListNode* pNode = pHead;
        while(pNode!=NULL)
        {	
            ListNode* pNext = pNode->next;
            bool needDelete = false;
            if(pNext!=NULL&&pNext->val==pNode->val)
                needDelete = true;
            if(!needDelete)
            {
                pPreNode = pNode;
                pNode = pNode->next;
            }
            else
        	{
             	int value = pNode->val;
                ListNode* pToBeDel = pNode;
                while(pToBeDel!=NULL&&pToBeDel->val==value)
                {
                    pNext = pToBeDel->next;
                    delete pToBeDel;
                    pToBeDel = NULL;
                    pToBeDel = pNext;
                }
                //
                if(pPreNode==NULL)
                    pHead = pNext;
                else
                    pPreNode->next = pNext;
                pNode = pNext;
            }
        }
        
       
        return pHead;
    }
};

发表于 2016-03-26 22:41:50 回复(0)

提交观点

问题信息

链表

难度：

1190条回答 2687收藏 147980浏览

通过挑战的用户

查看代码

xxxteb

2023-03-14 00:52:25
牛客58680...

2023-03-08 18:59:35
Elastic...

2023-02-13 21:51:56
YiLhh

2022-11-12 17:37:39
牛客57679...

2022-11-11 16:42:44

删除链表中重复的结点

输入

输出

输入

输出

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

思路

代码

问题信息

热门推荐

通过挑战的用户

相关试题