给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为
, 返回
.
给出的链表为
, 返回
.
例如：
给出的链表为
给出的链表为
数据范围：链表长度 
，链表中的值满足 
要求：空间复杂度 )
，时间复杂度
进阶：空间复杂度 )
，时间复杂度
[编程题]删除有序链表中重复的元素-II
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)
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){
if(p1.next.val==p1.next.next.val){
flag=true;
p1.next=p1.next.next;
}else if(flag){
flag=false;
p1.next=p1.next.next;
}else{
p1=p1.next;
}
}
if(flag){
p1.next=null;
}
return pre.next;
}
发表于 2023-05-14 16:17:57
回复(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)
public ListNode deleteDuplicates (ListNode head) {
// write code here
if (head == null)return null;
int [] Ppositions = new int[10000];
int [] Npositions = new int[10000];
int [] positionsHolder;
ListNode tempHead = head;
while (head != null) {
positionsHolder = head.val >= 0 ? Ppositions : Npositions;
positionsHolder[Math.abs(head.val)] = positionsHolder[Math.abs(head.val)] + 1;
head = head.next;
}
ListNode prev = null;
ListNode dummyHead = new ListNode(-1);
prev = dummyHead;
while (tempHead != null) {
positionsHolder = tempHead.val >= 0 ? Ppositions : Npositions;
if (positionsHolder[Math.abs(tempHead.val)] == 1) {
prev.next = tempHead;
prev = prev.next;
}
tempHead = tempHead.next;
}
prev.next = null;
return dummyHead.next;
}
过啦
发表于 2023-03-14 14:53:25
回复(0)
public class Solution {
public ListNode deleteDuplicates (ListNode head) {
if(head == null)
return null;
ListNode res = new ListNode(0);
res.next = head;
ListNode pre = res;
ListNode cur = head;
while(cur != null && cur.next != null){
//遇到相邻两个节点值相同
if(cur.val == cur.next.val){
int temp = cur.val;
//将所有相同的都跳过
while (cur != null && cur.val == temp){
cur = cur.next;
pre.next = cur;
}
}
else{
pre = pre.next;
cur = cur.next;
}
}
return res.next;
}
}
发表于 2023-03-07 15:25:17
回复(0)
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;
}
boolean flag=false;
ListNode h=new ListNode(0);
ListNode t=h;
ListNode pre=head;
ListNode p=head.next;
while(p!=null){
if(pre.val==p.val){
p=p.next;
flag=true;
}
else if(pre.val!=p.val&&flag==true){
pre=p;
p=p.next;
flag=false;
}
else if(pre.val!=p.val&&flag==false){
t.next=pre;
t=t.next;
t.next=null;
pre=p;
p=p.next;
flag=false;
}
}
if(flag==false){
t.next=pre;
}
return h.next;
}
}
发表于 2023-02-27 09:30:12
回复(0)
双指针进行判定，前后指针值相同则后指针后移，前指针不动。当值不相等且之前存在过值相等的情况，即index>0。则把前指针移到后指针位置，后指针+1。再借用test.next指示back的变化，从而得出结果。
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||head.next==null)
return head;
ListNode back = head;
ListNode front = head.next;
ListNode test = new ListNode(-1);
ListNode k = new ListNode(-1);
k = test;
test.next = head;
int index = 0;
while(front!=null)
{
if(front.val==back.val)
{
front = front.next;
index++;
continue;
}
if(index!=0)
{
back = front;
test.next = front;
front = back.next;
index=0;
continue;
}
back = back.next;
front = front.next;
test = test.next;
}
if(index!=0)
{
back = front;
test.next = front;
}
return k.next;
}
}
发表于 2023-02-22 10:20:56
回复(0)
问题信息
难度：
106条回答
1145收藏
25379浏览
通过挑战的用户
查看代码-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
