首页 > 试题广场 >

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

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

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

输入

{1,1,2}

输出

{1,2}
示例2

输入

{}

输出

{}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
查看答案及解析
添加回答
Java
又熬夜了的大学生很靠谱头像 又熬夜了的大学生很靠谱 
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

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 p=null,q=null;
        q=head;p=head.next;
        while(p!=null)
        {
            if(q.val==p.val)
            {
                p=p.next;
                q.next=p;
               
            }
            else{

                q=p;
                p=p.next;
            }
           
        }
        return head;
    }
}

首先判断该链表是否为空或者只有一个结点，若是则返回头指针即可。否则，定义两个指针分别q指向第一个节点和p指向第二个节点，依次进行判断。若，p.val!=q.val;p和q各向前走一步。若p.val==q.val,p向前走一步，q不动，q.next指向p.依次循环直到p为空时，返回head即可。
发表于 2024-04-24 18:05:38 回复(0)
Java
Lengxf_头像 Lengxf_ 
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

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 = new ListNode(-1);
        pre.next = head;
        while(head != null && head.next != null){
            if(head.val == head.next.val){
                head.next =  head.next.next;
            }else{
                head = head.next;
            }
        }
        return pre.next;
    }
}

编辑于 2023-12-05 11:35:34 回复(0)
Java
All_in_春招头像 All_in_春招
public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        ListNode q = head;
        while(q != null){
            while(q.next!=null && q.val == q.next.val){
                q.next = q.next.next;
            }
            q = q.next;
        }
        return head;
    }
}
发表于 2023-11-22 21:02:54 回复(0)
Java
李克雷头像 李克雷

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

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 fast = head.next, slow = head;
        while (fast != null) {
            if (fast.val == slow.val) {
                slow.next = fast.next;
                fast = fast.next;
            } else {
                fast = fast.next;
                slow = slow.next;
            }
        }
        return head;
    }
}
发表于 2023-10-11 15:48:46 回复(0)
Java
dqxfz头像 dqxfz
    public ListNode deleteDuplicates (ListNode head) {
        // 这里借鉴桶排序做法
        boolean[] exist = new boolean[202];
        ListNode h = head;
        ListNode dummy = new ListNode(0);
        dummy.next = h;
        ListNode prev = dummy;
        while(h != null) {
            int index = h.val;
            if (index < 0) {
                // 将负数转为正数
                index += 201;
            }
            if (exist[index]) {
                prev.next = h.next;
            } else {
                exist[index] = true;
                prev = h;
            }
            h = h.next;
        }
        return dummy.next;
    }
发表于 2023-09-13 10:22:56 回复(0)
Java
@唯时头像 @唯时 
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 = cur.next;
            } else {
                pre.next = cur;
                pre = pre.next;
                cur = cur.next;
            }
        }
        return head;
    }
}

发表于 2023-09-08 11:11:38 回复(0)
Java
Kanodayo头像 Kanodayo 
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        ListNode cur=head;
        if(cur==null){
            return head;
        }
        while(cur.next!=null){
            if(cur.val==cur.next.val){
                cur.next=cur.next.next;
            }
            else{
                cur=cur.next;
            }
        }
        return head;
    }

发表于 2023-08-09 14:38:25 回复(0)
Java
做则必成的勇气和信心头像 做则必成的勇气和信心 
public ListNode deleteDuplicates (ListNode head) {
        // 删除重复元素，链表有序
        ListNode dummy=new ListNode(-1);
        dummy.next=head;
        ListNode cur=head;
        while(cur!=null&&cur.next!=null){
            if(cur.val==cur.next.val){
                cur.next=cur.next.next;//删掉重复元素
            }else{
                cur=cur.next;//不删重复元素
            }
        }
        return dummy.next;

    }

发表于 2023-07-18 15:31:57 回复(0)
Java
抓住努力的尾巴头像 抓住努力的尾巴 
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        //1、判断头节点是否为空
        if (head == null) {
            return null;
        }
        //2、构造一个虚拟头节点
        ListNode newHead = new ListNode(-1);

        ListNode cur = head;
        ListNode tmp = newHead;

        //3、遍历链表
        while (cur != null) {
            if (cur.next != null && cur.val == cur.next.val) {
                while (cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
            } else {
                tmp.next = cur;
                tmp = tmp.next;
                cur = cur.next;
            }
        }
        tmp.next = null;
        return newHead.next;
    }
}
发表于 2023-07-10 13:03:32 回复(0)
Java
_ther头像 _ther 
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // 遍历head

        Set<Integer> set = new LinkedHashSet<>();

        while (head != null) {
            set.add(head.val);
            head = head.next;
        }

        ListNode result = null;
        ListNode current = null;
        int count = 0;

        // 遍历set集合
        for (Integer s : set) {
            if (count == 0) {
                // 第一个节点
                current = new ListNode(s);
                // 记录下第一个节点
                result = current;
            } else {
                ListNode next = new ListNode(s);
                // 将下一个节点加进来
                current.next = next;
                // 移动头节点到下一个节点
                current = current.next;
                // System.out.println(s);
            }
            count++;
        }

        return result;
    }


发表于 2023-06-24 22:52:29 回复(0)
Java
懒牪头像 懒牪 
public class Solution {
    /**
     * 
     * 单子指针
     */
     public ListNode deleteDuplicates (ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode fore = head;
        while(fore.next != null){
            if(fore.val == fore.next.val){
                fore.next =fore.next.next;
            }else{
                fore = fore.next;
            }
        }
        return head;
    }


    //双指针
    public ListNode deleteDuplicates (ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode fore = head,back = head.next;
        while(back != null){
            if(fore.val == back.val){
                fore.next = back.next;
                back = back.next;
            }else{
                fore = fore.next;
                back = back.next;
            }
        }
        return head;
    }
}

发表于 2023-05-04 14:24:25 回复(0)
Java
拒绝pua的小蜗牛很想潜水头像 拒绝pua的小蜗牛很想潜水
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;
        ListNode pre = new ListNode(-101);
        pre.next = head;
        ListNode cur = pre.next;
        while (cur != null && cur.next != null) {
            while ((cur != null && cur.next != null) &&
                    cur.val == cur.next.val)cur.next = cur.next.next;
            cur = cur.next;
        }
        return pre.next;
    }
}
发表于 2023-04-01 20:20:22 回复(0)
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)
Java
呸，看见你就开心头像 呸，看见你就开心 
import java.util.*;
public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        if(head == null){
            return null;
        }
        //相同跳过，不相等继续走
        ListNode cur = head;
        while(cur!=null && cur.next!=null){
            if(cur.val == cur.next.val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return head;
    }
}

发表于 2023-03-21 23:21:18 回复(0)
Java
BlueProtocol头像 BlueProtocol 
public class Solution {
    /**
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        if (head == null) return null;
        List<Integer> list = new ArrayList();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        List<Integer> distinctList = list.stream().distinct().collect(
                                         Collectors.toList());
        ListNode sentinel = new ListNode(-1);
        ListNode cur = sentinel;
        for (int i = 0; i < distinctList.size(); i++) {
            cur.next = new ListNode(distinctList.get(i));
            cur = cur.next;
        }
        return sentinel.next;
    }
}

发表于 2023-03-18 09:56:32 回复(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) {
        if(head == null)return null;

        // hash去除链表重复元素
        TreeSet<Integer> set = new TreeSet<>();
        while(head != null){
            set.add(head.val);
            head = head.next;
        }
        ListNode list = new ListNode(set.first());
        ListNode newHead = list;
        set.remove(set.first());
        //从第二个元素开始遍历
        for(Integer val : set){
            newHead.next = new ListNode(val);
            newHead = newHead.next;
        }
        return list;
    }
}

发表于 2023-03-13 23:02:59 回复(0)
Java
躺平了的柯基很坦荡头像 躺平了的柯基很坦荡 
public ListNode deleteDuplicates (ListNode head) {
        // write code here
        if(head == null){
            return null;
        }
        ListNode cur = head;
        //使用 set集合来删除重复元素，hashSet是无序的，而LinkedHashSet是有序的；
        LinkedHashSet<Integer> hashSet = new LinkedHashSet<>();
        while (cur != null){
             hashSet.add(cur.val);
             cur = cur.next;
        }
        cur = head;
        ListNode tmp = null;
        for (Integer e : hashSet){
            cur.val = e;
            tmp = cur;
            cur = cur.next;
        }
        tmp.next = null;
        
        return head;
    }

发表于 2023-02-11 00:45:11 回复(0)
提交观点

问题信息

链表
难度：
84条回答 26997浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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