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

Java

牛客865904219号

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        // 使用双指针
        if(head == null) return null;
        ListNode resHead = null; // 这个头 需要在pre第一次被指定值时，指定
        ListNode pre = null;
        ListNode remeberNode = null; // 记忆节点， 每次发现前后节点不重复时，设置为null

        while(head != null){

            // 记忆节点什么时候给值，什么时候重制，以及在判断中的作用
            ListNode next = head.next;
            head.next = null;
            if(next != null && head.val == next.val){
                remeberNode = head;
            }else{
                // 记忆节点没有值，说明pre 节点可以移动；
                if (remeberNode == null){
                    if(pre == null) {
                        pre = head;
                        resHead = head;
                    }else{
                        pre.next = head;
                        pre = head;
                    }
                    
                }

                remeberNode = null;
            }
            head = next;
        }
        
        return resHead;
    }
}

发表于 2025-06-23 15:39:11 回复(0)

Java

在攒经验的打工鸭很伤心

ListNode res=new ListNode(-1001),cur=res,pre=res;
while(head!=null){
    if(head.val!=pre.val&&(head.next==null||head.val!=head.next.val)){
        cur.next=head;
        cur=cur.next;
    }
    pre=head;
    head=head.next;
}
cur.next=null;
return res.next;

发表于 2025-05-11 17:56:41 回复(0)

Java

牛客229962883号

核心思路是保证所有后续节点的有序：

   public ListNode deleteDuplicates (ListNode head) {

        if (head == null) {
            return head;
        }

        // write code here
        int origin = head.val - 1;
        ListNode pre = new ListNode(origin);
        pre.next = head;
…            noneDel = pre;
            pre = pre.next;
        }


        return del.next;
    }

发表于 2025-03-15 14:26:43 回复(0)

Java

୧⍢⃝୨

    public ListNode deleteDuplicates (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        Map<Integer, Integer> map = new HashMap<>();
        ListNode p = head;
        while (p != null) {
            map.put(p.val, map.getOrDefault(p.val, 0) + 1);
            p = p.next;
        }
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode pre = dummyHead;
        p = head;
        while (p != null) {
            while (p != null && map.get(p.val) > 1) {
                p = p.next;
            }
            pre.next = p;
            pre = p;
            p = p == null ? null : p.next;
        }
        return dummyHead.next;
    }
}

发表于 2024-09-18 11:18:29 回复(1)

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

        // 借助容器，要求该容器：能统计次数（HashMap）

        // 算法的时间复杂度O(N)，额外空间复杂度O(N)

        // 1.处理特殊链表
        if (head == null || head.next == null) {
            // 对于空链表，单结点链表，直接返回head
            return head;
        }

        // 2.遍历链表，统计结点的值与对应的出现次数
        HashMap<Integer, Integer> countMap = new HashMap<>();
        ListNode cur = head;
        while (cur != null) {
            if (!countMap.containsKey(cur.val)) {
                // 如果HashMap中没有这个key，说明是第一次出现
                countMap.put(cur.val, 1);
            } else {
                // 如果HashMap中有这个key，说明是并非第一次出现
                int count = countMap.get(cur.val);
                count++;
                countMap.put(cur.val, count);
            }
            cur = cur.next;
        }

        // 3.再次遍历链表，找出其值只出现过1次的结点，将其连接起来
        // 3.1 先把head定位到链表中第一个其值只出现了一次的结点
        cur = head;
        head = null;
        while (cur != null) {
            if (countMap.get(cur.val) == 1) {
                // 当前结点的值只出现了一次
                head = cur;
                break;
            }
            cur = cur.next;
        }
        if (head == null) {
            // 如果遍历了一轮链表，发现head还是null，说明整个链表全是值重复结点
            return null;
        }
        // 3.2 此时，head和cur指向了第一个不重复结点，继续遍历链表，使用尾插法持续纳入不重复结点
        ListNode tail = head;
        cur = cur.next;
        while (cur != null) {
            if (countMap.get(cur.val) == 1) {
                // 当前结点只出现了一次
                tail.next = cur;
                tail = cur;
            }
            cur = cur.next;
        }
        // 3.3 给最后一个结点的next指向null，防止带出来值重复的结点
        tail.next = null;

        // 4.返回头部
        return head;
    }
}

发表于 2024-07-27 14:17:40 回复(0)

Java

狂野的小狮子

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        ListNode tempHead = new ListNode(0);
        tempHead.next = head;

        ListNode p = head, pre = tempHead;
        while (p != null && p.next != null) {
            if (p.val == p.next.val) {
                while (p.next != null && p.val == p.next.val) {
                    p = p.next;
                }
                pre.next = p.next;
                p = pre.next;
            } else {
                pre = p;
                p = p.next;
            }
        }
        return tempHead.next;
    }
}

发表于 2024-06-11 13:33:36 回复(0)

Java

牛客839384289号

public ListNode deleteDuplicates (ListNode head) {
    // write code here
    ListNode pre=new ListNode(0) ,p1=pre;
    pre.next=head;
    boolean flag=false;
    while(p1.next!=null && p1.next.next!=null){
        while(p1.next!=null && p1.next.next!=null && p1.next.val==p1.next.next.val){
            p1.next=p1.next.next;
            flag=true;
        }
        if(flag){
            p1.next=p1.next.next;
            flag=!flag;
        }else{
            p1=p1.next;
        }
    }
    return pre.next;
}

发表于 2024-06-02 14:58:58 回复(0)

Java

牛客528077103号

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

ListNode beforeNode = new ListNode(0);

beforeNode.next = head;

ListNode preNode = beforeNode;

if(beforeNode.next == null || beforeNode.next.next == null){

return beforeNode.next;

}

while(preNode.next != null && preNode.next.next != null){

if(preNode.next.val == preNode.next.next.val){

//因为当前节点是从before开始，所以判断将下个节点的赋值给temp

int temp = preNode.next.val;

//下个节点之后的每个节点的值都跟temp 比较，相等指针右移

while(preNode.next != null && preNode.next.val== temp){

preNode.next = preNode.next.next;

}

}else{

//如果当时节点不等于下一个节点，指针指向下个节点

preNode = preNode.next;

}

return beforeNode.next;

}

发表于 2024-04-07 20:13:32 回复(0)

Java

疯狗侠

import java.util.*;
public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode list = new ListNode(-1);
        ListNode rear = list;
        ListNode pre = head;
        ListNode p = head.next;
        while(p != null){
            if(pre.val != p.val){
                if(pre.next == p){
                    rear.next = pre;
                    rear = rear.next;
                }
                pre = p;      
            }
            p = p.next;
        }
        if(pre.next == null)
            rear.next = pre;
        else
            rear.next = null;
        return list.next;
    }
}

发表于 2023-12-24 14:59:49 回复(0)

Java

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

编辑于 2023-12-05 16:00:56 回复(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 dummy = new ListNode(0);
        dummy.next = head;
        ListNode pos = head;
        ListNode preStart = dummy;
        while (pos != null && pos.next != null) {
            if (pos.val == pos.next.val) {
                while (pos != null && pos.next != null && pos.val == pos.next.val) {
                    pos.next = pos.next.next;
                }
                preStart.next = pos.next;
                pos = pos.next;     
            } else {
                preStart = pos;
                pos = pos.next;
            }
        }

        return dummy.next;

    }
}

发表于 2023-11-27 22:14:14 回复(0)

Java

BlueProtocol

好理解的方法

    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        if(head == null) return head;
        ListNode sentinel = new ListNode(-1);
        sentinel.next = head;
        ListNode first = sentinel.next.next;
        ListNode second = sentinel.next;
        ListNode wait = sentinel;
        boolean isOper = false;
        while(first!=null && second!=null) {
            if(second.val != first.val) {
                first = first.next;
                second = second.next;
                if(isOper == false) {
                    wait = wait.next;
                }
                isOper = false;
            }else{
                while(first!=null&&second.val==first.val) {
                    first = first.next;
                }
                wait.next = first;
                second = wait;
                isOper = true;
            }
        }
        return sentinel.next;
    }

发表于 2023-11-04 23:24:36 回复(0)

Java

最美不过初见2

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
        ListNode res=new ListNode(-1);
        ListNode tail=res;
        ListNode p=head;
        boolean flag=false;
        while(p!=null&&p.next!=null){
            if(p.val==p.next.val){
                flag=true;
                p=p.next;
            }else if(p.val!=p.next.val&&flag){
                p=p.next;
                flag=false;
            }else if(p.val!=p.next.val&&!flag){
                ListNode tmp=p.next;
                tail.next=p;
                p.next=null;
                tail=p;
                p=tmp;
            }
        }
        if(p==null){
            return res.next;
        }else if(p.next==null){
            if(flag){
                return res.next;
            }else{
                ListNode tmp=p;
                p.next=null;
                tail.next=p;
                tail=p;
                p=tmp;
            }
        }
        return res.next;
    }
}

发表于 2023-10-26 13:23:24 回复(0)

Java

wxyld

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) {

return head;

}

// 不知道何时为头，自己设置一个头

ListNode res = new ListNode(0);

ListNode temp = res;

// 标记是否当前元素是否重复过

int flag = 0;

while (head != null && head.next != null) {

if (head.val == head.next.val) {

head = head.next;

flag = 1;

// 即使当前元素与下一个元素不相等，只要当前元素重复过，就不要

} else if (flag == 1) {

head = head.next;

flag = 0;

// 当前元素与下一个元素不相等，且没有重复过，存入res

} else {

temp.next = head;

temp = temp.next;

head = head.next;

}

// 判断最后一个元素是否需要存入

if (flag == 0) {

temp.next = head;

temp = temp.next;

}

// 将res与head断开

temp.next = null;

return res.next;

}

发表于 2023-08-14 15:11:03 回复(0)

Java

做则必成的勇气和信心

public ListNode deleteDuplicates (ListNode head) {
        if(head==null) return null;
        ListNode dummy=new ListNode(-1);
        dummy.next=head;
        ListNode pre=dummy;
        ListNode cur=head;
        while(cur!=null&&cur.next!=null){
            if(cur.val==cur.next.val){
                int tmp=cur.val;//记录下这个相同的值
                while(cur!=null&&cur.val==tmp){//去掉所有相同的值
                    cur=cur.next;
                    pre.next=cur;
                }
            }else{//如果没有相同的值
                cur=cur.next;
                pre=pre.next;
            }
        }
        return  dummy.next;
    }

发表于 2023-07-18 17:04:15 回复(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;
                }
                cur = cur.next;
            } else {
                tmp.next = cur;
                tmp = tmp.next;
                cur = cur.next;
            }
        }
        tmp.next = null;
        return newHead.next;
    }
}

发表于 2023-07-10 13:01:10 回复(0)

Java

牛客346253966号

/**
     * 保留只出现一次的元素
     */
    public ListNode deleteDuplicates(ListNode head) {
        // 如果链表为空或只有一个节点，直接返回
        if (head == null || head.next == null) return head;

        // 添加头节点，方便处理第一个节点就是重复节点的情况
        ListNode nullHead = new ListNode(-1);
        nullHead.next = head;
        // pre 指向当前不重复的节点，cur 指向当前节点，num_flag 记录当前不重复的节点的值
        ListNode pre = nullHead;
        ListNode cur = head;
        int num_flag = head.val;
        // del_flag 记录当前节点是否需要删除
        boolean del_flag = false;
        while (cur.next != null) {
            // 如果当前节点的值与 num_flag 相同，说明当前节点是重复节点，需要删除
            if (cur.next.val == num_flag) {
                del_flag = true;
                cur.next = cur.next.next; // 删除当前节点
            } else {
                // 如果当前节点不是重复节点，根据 del_flag 判断是否需要删除 pre 节点
                if (del_flag) {
                    pre.next = cur.next; // 删除 pre 节点
                    cur = cur.next; // cur 指向下一个节点
                    del_flag = false; // 重置 del_flag
                } else {
                    // 如果当前节点不是重复节点且 pre 节点不需要删除，pre 和 cur 都向后移动
                    cur = cur.next;
                    pre = pre.next;
                }
                // 更新 num_flag 的值
                num_flag = cur.val;
            }
        }
        // 如果最后一个节点需要删除，将 pre 的 next 置为 null
        if (del_flag) {
            pre.next = null;
        }
        // 返回去掉头节点的链表
        return nullHead.next;
    }

发表于 2023-05-26 10:31:50 回复(0)

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

输入

输出

输入

输出

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

问题信息

热门推荐

通过挑战的用户

相关试题