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

720个回答

添加回答
参考了大家的代码
public class Solution {
	public ListNode deleteDuplication(ListNode pHead) {
		if (pHead == null || pHead.next == null) { // 只有0个或1个结点,则返回
			return pHead;
		}
		if (pHead.val == pHead.next.val) { // 当前结点是重复结点
			ListNode pNode = pHead.next;
			while (pNode != null && pNode.val == pHead.val) {
				// 跳过值与当前结点相同的全部结点,找到第一个与当前结点不同的结点
				pNode = pNode.next;
			}
			return deleteDuplication(pNode); // 从第一个与当前结点不同的结点开始递归
		} else { // 当前结点不是重复结点
			pHead.next = deleteDuplication(pHead.next); // 保留当前结点,从下一个结点开始递归
			return pHead;
		}
	}
}

发表于 2016-09-20 13:14:55 回复(36)
递归
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if (pHead==NULL)
            return NULL;
        if (pHead!=NULL && pHead->next==NULL)
            return pHead;
                
        ListNode* current;
        
        if ( pHead->next->val==pHead->val){
            current=pHead->next->next; 
            while (current != NULL && current->val==pHead->val)
                current=current->next;
            return deleteDuplication(current);                      
        }
        
        else {
            current=pHead->next;
            pHead->next=deleteDuplication(current);
            return pHead;
        }     
    }
};

发表于 2016-03-30 19:41:52 回复(51)
public static ListNode deleteDuplication(ListNode pHead) {
		
        ListNode first = new ListNode(-1);//设置一个trick

		first.next = pHead;

		ListNode p = pHead;
		ListNode last = first;
		while (p != null && p.next != null) {
			if (p.val == p.next.val) {
				int val = p.val;
				while (p!= null&&p.val == val)
					p = p.next;
				last.next = p;
			} else {
				last = p;
				p = p.next;
			}
		}
		return first.next;
	}

编辑于 2015-08-27 20:49:38 回复(68)

非递归的代码:

1. 首先添加一个头节点,以方便碰到第一个,第二个节点就相同的情况

2.设置 pre ,last 指针, pre指针指向当前确定不重复的那个节点,而last指针相当于工作指针,一直往后面搜索。

        if (pHead==null || pHead.next==null){return pHead;}
        ListNode Head = new ListNode(0);
        Head.next = pHead;
        ListNode pre  = Head;
        ListNode last = Head.next;
        while (last!=null){
            if(last.next!=null && last.val == last.next.val){
                // 找到最后的一个相同节点
                while (last.next!=null && last.val == last.next.val){
                    last = last.next;
                }
                pre.next = last.next;
                last = last.next;
            }else{
                pre = pre.next;
                last = last.next;
            }
        }
        return Head.next;
编辑于 2018-03-14 22:04:21 回复(4)
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
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;//返回头结点的下一个节点
              
          }
    }
};

发表于 2016-07-26 10:58:06 回复(22)


剑指offer没看,不知道是不是用的这个方法。
看懂了这个图,就明白了。
1.加一个头结点
2.两个临时指针p,q
3.找前后不相等的节点
class Solution {
public:
	ListNode* deleteDuplication(ListNode* pHead)
	{
		if (pHead == NULL || pHead->next == NULL)
			return pHead;

		/*---------先为链表创建一个头结点---------*/

		int firstNumber = pHead->val;

		//假设我的头结点数值为-1
		int myFirst = -1;

		//万一链表的头结点也为-1,那么我就改成-2
		if (myFirst == firstNumber)
		{
			
			myFirst = -2;
		}
		ListNode *head = new ListNode(myFirst);
		head->next = NULL;
		head->next = pHead;

		ListNode *p = head;
		ListNode *q = head->next;

		while (q)
		{
			while (q->next && (q->next->val == q->val))
			{
				q = q->next;
			}
			if (p->next != q)
			{
				
				q = q->next;
				p->next = q;
			}
			else 
			{
				p = q;
				q = q->next;
			}
		}

		//返回的时候,注意去掉头结点(自己创建的辅助节点)
		return head->next;

	}
};

编辑于 2016-09-12 01:53:23 回复(22)
# -*- 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 回复(8)
//为方便操作,加一个头结点,最后再删掉
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead){
        ListNode* head=new ListNode(0);
        ListNode* p=head;
        ListNode* q=pHead;
        while(q){
            while(q!=NULL&&q->next!=NULL&&q->next->val==q->val){
                int tmp=q->val;
                while(q!=NULL&&q->val==tmp)
                    q=q->next;
            }
            p->next=q; 
            p=p->next;
            if(q)
                q=q->next;
        }    
        return head->next;
    }
};

发表于 2017-06-08 19:53:29 回复(2)
//q、p、r代表上个节点,当前节点,后继节点
public ListNode deleteDuplication(ListNode pHead) {
		ListNode q, p, r;
		p = pHead;
		q = r = null;

		while (p != null) {
			boolean flag = false;
			r = p.next;
			while (r != null && r.val == p.val) {
				flag = true;
				r = r.next;
			}
			if (flag) {
				if (q != null)
					q.next = r;
				else
					pHead = null;
			} else {
				if (q == null)
					pHead = p;
				q = p;
			}
			p = r;
		}

		return pHead;
}

编辑于 2016-03-31 09:31:57 回复(4)
思考:化繁为简,先找到第一个符合的结点,以后递归。

 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 回复(3)

python solution:

先不管三七二十一把所有节点的值放到一个列表中,再筛选出值数量为1的值。

再新建一个链表返回即可。很暴力。

class Solution:
    def deleteDuplication(self, pHead):
        res = []
        while pHead:
            res.append(pHead.val)
            pHead = pHead.next
        res = list(filter(lambda c: res.count(c) == 1, res))
        dummy = ListNode(0)
        pre = dummy
        for i in res:
            node = ListNode(i)
            pre.next = node
            pre = pre.next
        return dummy.next
编辑于 2017-10-19 19:41:46 回复(16)
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)
/*
*因为需要删除重复的节点,所以需要保留一个待删除节点之前的节点,这里用一个指针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)
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 回复(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版递归
    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)
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)
/*
 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)
两种实现


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)