首页 > 试题广场 >

删除有序链表中重复的元素-I

[编程题]删除有序链表中重复的元素-I
  • 热度指数：161691 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次
例如：
给出的链表为,返回.
给出的链表为,返回.

数据范围：链表长度满足 ，链表中任意节点的值满足
进阶：空间复杂度 ，时间复杂度
示例1

输入

{1,1,2}

输出

{1,2}
示例2

输入

{}

输出

{}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
查看答案及解析
添加回答
勇敢牛牛，不怕困难！头像 勇敢牛牛，不怕困难！ 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
  /**
   * 
   * @param head ListNode类 
   * @return ListNode类
   */
  ListNode* deleteDuplicates(ListNode* head) {
    // 维护住循环不定式(loop invariant)
    // 从头指针指向的节点到curr指向的节点之间不存在重复的元素!
    ListNode* curr = head;
    while (curr && curr->next) {
      if (curr->val == curr->next->val) {
        ListNode* node_to_delete = curr->next;
        curr->next = curr->next->next;
        delete node_to_delete;
      } else {
        curr = curr->next;
      }
    }
    return head;
  }
};

发表于 2021-07-06 14:22:14 回复(0)
Java
肥猿头像 肥猿
解题思路：从表头开始遍历，如果出现两个相邻节点数值相等，则跳过当前节点 
import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */
public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        if(head==null||head.next==null) return head;
        ListNode pre=head;
        ListNode cur=head.next;
        while(cur!=null){
            if(pre.val==cur.val){
                pre.next=cur.next;
                cur=pre.next;
            } else{
                pre=cur;
                cur=cur.next;
            }
        }
        return head;
    }
}


发表于 2021-03-20 16:16:55 回复(0)
RmondJone头像 RmondJone 
import java.util.*;

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

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        if(head==null){
           return null; 
        }
        Set<Integer> set=new HashSet<Integer>();
        ListNode temp=head;
        while(temp!=null){
           set.add(temp.val);
           temp=temp.next; 
        }
        List<Integer> list=new ArrayList<Integer>(set);
        Collections.sort(list);
        ListNode temp1=new ListNode(list.get(0));
        ListNode retNode=temp1;
        for(int i=1;i<list.size();i++){
           retNode.next=new ListNode(list.get(i));
           retNode=retNode.next; 
        }
        return temp1;
    }
}

发表于 2021-01-21 17:10:33 回复(0)
keeprealandconfidence头像 keeprealandconfidence
思路是以当前结点的值为依据，向后查找，直到找到值不相等的结点。代码如下： 
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode * p=head;
        while(p!=NULL&&p->next!=NULL)
        {
            ListNode * q=p->next;
            while(q!=NULL&&q->val==p->val)
            {
                q=q->next;
            }
            p->next=q;
            p=q;
        }
        return head;
    }
};


发表于 2019-08-08 20:44:00 回复(1)
C/C++
nbgao头像 nbgao 
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
		if(head == NULL || head->next == NULL)
			return head;
			
		ListNode *p = head,*q;

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

发表于 2017-08-05 01:48:28 回复(0)
元气の悟空头像 元气の悟空 
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        vector<int> d;
        map<int,int> book;
        ListNode *p,*p1;
        int i;
        for(p=head;p;p=p->next)
            if(book.count(p->val)==0)
            {
            	d.push_back(p->val);
            	book[p->val]=1;
        	}
        if(d.size()==0) return NULL;
        for(i=0,p=p1=head;i<d.size();p->val=d[i],i++,p1=p,p=p->next);
        p1->next=NULL;
        return head;
    }
};

发表于 2016-08-14 21:06:56 回复(1)
NothingCoder头像 NothingCoder 
public ListNode deleteDuplicates(ListNode head) {
		
		ListNode cur = head;
		while(cur != null){
			while(cur.next != null && cur.val == cur.next.val){
				cur.next = cur.next.next;
			}
			cur = cur.next;
		}
		return head;
	}

发表于 2016-07-19 17:18:21 回复(23)
此广告位出租头像 此广告位出租 
        ListNode p=head,q=head;
        while (p != null && q != null){
            if (q.val == p.val){
                p.next = q.next;
            } else {
                p = p.next;
            }
            q = q.next;
        }
        return head;

编辑于 2018-05-22 14:49:19 回复(0)
萨达哈鲁头像 萨达哈鲁 
public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        ListNode tou = head;
        while(head != null && head.next != null) {
            if(head.val == head.next.val) {
                head.next = head.next.next;
            } else {
                head = head.next;
            }
        }
        return tou;
    }
}
一个while搞定得了。重复的就不往后走，一直删。不重复指针在往后移动一位即可。
发表于 2020-06-29 08:21:25 回复(0)
C/C++
QT菜鸡弟弟头像 QT菜鸡弟弟 
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode *cur = head;
        while(cur != NULL){
            while(cur->next != NULL && cur->val == cur->next->val){
                cur->next = cur->next->next;
            }
            cur = cur->next;
        }
        return head;
    }
};

发表于 2019-09-20 10:24:32 回复(0)
Java
Nakangzi头像 Nakangzi 
public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        if(head==null||head.next==null)return head;
        ListNode cur=head;
        while(cur!=null&&cur.next!=null){
            if(cur.next.val==cur.val){
                cur.next=cur.next.next;
            }
            else cur=cur.next;
        }
        return head;
    }
}

发表于 2020-08-25 17:46:32 回复(2)
C/C++
努力的牛牛头像 努力的牛牛 
    /*
    * 目的：删除链表中重复元素，只保留一次
    * 方法：新建一个头节点，
    *      如果当前节点与next节点的值相等，则分别移至下一个节点，
    *      否则插入到新的链表中，最后返回dummy.next
    */
    ListNode *deleteDuplicates(ListNode *head) {
        if (head == nullptr)
            return head;
        ListNode dummy(-1);
        ListNode*pre = &dummy;
        ListNode*next =nullptr;
        while(head){
            next = head->next;
            if (next==nullptr || head->val != next->val)
            {
                head->next = nullptr;
                pre->next = head;
                pre=pre->next;
            }
            head=next;
        }
        return dummy.next;
    }
发表于 2019-12-09 09:32:00 回复(0)
C/C++
JordanBelfort头像 JordanBelfort 
//要断开无用的指针,防止内存泄露
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if(head == NULL || head->next == NULL) return head;
        ListNode* p1 = head;
        while(p1 != NULL && p1->next != NULL) {
            ListNode* p2 = p1->next;
            if(p1->val != p2->val) {
                p1->next = p2;
                p1 = p1->next;
                continue;
            }
            while(p2->next != NULL && p1->val == p2->next->val) p2 = p2->next;
            p1->next = p2->next;
            delete p2;
            p1 = p1->next;
        }
        return head;
    }
};

编辑于 2017-03-10 14:55:15 回复(1)
Java
Sillyou头像 Sillyou
import java.util.*;
public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        ListNode p = head;
        // && 运算符：若左编false，就不会判断右边
        while(p != null && p.next != null) {
            if(p.val == p.next.val) {
                p.next = p.next.next;
            } else {
                p = p.next;
            }
        }
        return head;
    }
}
发表于 2023-03-28 17:26:58 回复(0)
Python3
牛客1217718号头像 牛客1217718号
class Solution:
    def deleteDuplicates(self , head: ListNode) -> ListNode:
        cur = head
        while cur and cur.next:
            nex = cur.next
            if nex.val <= cur.val:
                cur.next = nex.next
            else:
                cur = nex
        return head
发表于 2022-09-30 21:51:48 回复(0)
Java
玄鉴头像 玄鉴 
import java.util.*;

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

public class Solution {
    /**
     *
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode node=dummy;
        while(node.next!=null&&node.next.next!=null){
            if(node.next.val==node.next.next.val){
                node=node.next;
                int x=node.next.val;
                while(node.next!=null&&node.next.val==x){
                    node.next=node.next.next;
                }
            }
        else node=node.next;
    }
        return dummy.next;
}
}

如果要删除 所有存在重复的元素

import java.util.*;

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

public class Solution {
    /**
     *
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode node=dummy;
        while(node.next!=null&&node.next.next!=null){
            if(node.next.val==node.next.next.val){
                //node=node.next; 把这一行注释掉即可。
                int x=node.next.val;
                while(node.next!=null&&node.next.val==x){
                    node.next=node.next.next;
                }
            }
        else node=node.next;
    }
        return dummy.next;
}
}
发表于 2021-12-23 23:41:10 回复(0)
Java
小灰灰QAQ头像 小灰灰QAQ 
  public ListNode deleteDuplicates(ListNode head) {
        if (head == null)
            return null;
        ListNode p = head;
        while (p.next != null) {
            if (p.next.val == p.val)
                p.next = p.next.next;
            else {
                p = p.next;
            }
        }
        return head;
    }

发表于 2021-12-13 16:00:19 回复(0)
C++
xxining头像 xxining 
class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr) return head;
        ListNode* cur = head;
        ListNode* nex = head->next;
        while(nex){
            if(cur->val == nex->val){
                cur->next = nex->next;
            }else{
                cur = nex;
            }
            nex = nex->next;
        }
        return head;
    }
};

发表于 2021-12-10 01:51:50 回复(0)
cqu后起之秀头像 cqu后起之秀 
class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
        if(head == NULL) return head;
        ListNode *cur = NULL, *list = head,*next = NULL;
        while(list){
            while(list->val == list->next->val && list->next != NULL){
                cur = list->next->next;
                list->next->next = NULL;
                list->next = cur;
            }
            list = list->next;
        }
        return head;
    }
};

发表于 2021-07-06 00:00:49 回复(0)
JavaScript
IPzzzi头像 IPzzzi 
function deleteDuplicates( head ) {
    // write code here
    if(head == null){
        return head;
    }
    var p = head;
    while(p.next !== null){
        if(p.next.val == p.val){
            p.next = p.next.next;
        }else{
            p = p.next;
        }
    }
    return head;
}

发表于 2021-04-12 20:31:14 回复(0)
提交观点

问题信息

链表
难度：
362条回答 26891浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号