给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为
, 返回
.
给出的链表为
, 返回
.
例如：
给出的链表为
给出的链表为
数据范围：链表长度 
，链表中的值满足 
要求：空间复杂度 )
，时间复杂度
进阶：空间复杂度 )
，时间复杂度
[编程题]删除有序链表中重复的元素-II
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)
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)
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)
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)
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)
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)
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)
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)
好理解的方法
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)
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)
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)
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)
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)
/**
* 保留只出现一次的元素
*/
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)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @return ListNode类
*/
public static ListNode deleteDuplicates(ListNode head) {
ListNode ptr = head;
ListNode fastPtr = ptr;
ListNode repeatStartNode = null;
ListNode repeatEndNode = null;
if (ptr == null) {
return head;
}
do {
if (ptr != null) {
int count = 0;
do {
if (fastPtr != null) {
if (ptr != fastPtr && ptr.val == fastPtr.val) {
repeatStartNode = ptr;
repeatEndNode = fastPtr;
count++;
} else {
if (count > 0) {
head = removeNode(head, repeatStartNode, repeatEndNode);
}
}
fastPtr = fastPtr.next;
}
} while (fastPtr != null);
if (count > 0 && repeatStartNode != null && repeatEndNode != null) {
head = removeNode(head, repeatStartNode, repeatEndNode);
repeatStartNode = null;
repeatEndNode = null;
}
if (count > 0) {
ptr = head;
} else {
ptr = ptr.next;
fastPtr = ptr;
}
}
} while (ptr != null);
return head;
}
private static ListNode removeNode(ListNode head, ListNode repeatStartNode,
ListNode repeatEndNode) {
if (repeatStartNode == null || repeatEndNode == null) {
return head;
}
ListNode ptr = head;
do {
if (ptr != null) {
if (ptr == head && ptr == repeatStartNode) {
head = repeatEndNode.next;
break;
}
if (ptr.next == repeatStartNode) {
ptr.next = repeatEndNode.next;
break;
}
ptr = ptr.next;
}
} while (ptr != null);
return head;
}
} 头大
发表于 2023-04-26 11:16:20
回复(0)
import java.util.*;
public class Solution {
public ListNode deleteDuplicates (ListNode head) {
// 先遍历记录重复数据于哈希表中，再次遍历去重
// 创建哈希表
HashMap<Integer,Integer> map = new HashMap<>();
if(head == null){return null;} //假如输入head为空
// 遍历记录数据
ListNode i = head;
while(i.next != null){
if(i.val == i.next.val){
map.put(i.val,1);
}
i = i.next;
}
// 创建虚拟头节点，方便删除原头节点
ListNode pre = new ListNode(0);
pre.next = head;
ListNode cur = pre;
// 遍历删除数据
while(cur.next != null){
if(map.containsKey(cur.next.val)){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
return pre.next;
}
}
发表于 2023-03-19 00:23:12
回复(0)
问题信息
难度：
110条回答
1259收藏
26277浏览
通过挑战的用户
查看代码-
2023-02-17 15:00:23 -
2022-11-23 18:33:38 -
2022-10-10 18:07:32 -
2022-09-20 14:48:28
-
2022-09-19 13:26:26
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
