删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次
例如：
给出的链表为
,返回
.
给出的链表为
,返回
.
例如：
给出的链表为
给出的链表为
数据范围：链表长度满足 
，链表中任意节点的值满足 
进阶：空间复杂度 )
，时间复杂度 )
[编程题]删除有序链表中重复的元素-I
public class Solution {
public ListNode deleteDuplicates (ListNode head) {
ListNode dummyHead = new ListNode(-101);
dummyHead.next = head;
ListNode pre = dummyHead;
ListNode p = dummyHead.next;
HashSet<Integer> set = new HashSet<>();
while (p != null) {
if (!set.contains(p.val)) {
set.add(p.val);
pre = p;
p = p.next;
} else {
pre.next = p.next;
p = p.next;
if (p != null && p.val != pre.val) {
set.add(p.val);
pre = p;
p = p.next;
}
}
}
return dummyHead.next;
}
}
发表于 2024-09-18 10:51:43
回复(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) {
if(head == null || head.next == null)
return head;
// write code here
ListNode p = head;
int value = head.val;
while(p.next!=null){
if(p.next.val == p.val){
p.next = p.next.next;
}else{
p = p.next;
}
}
return head;
}
}
发表于 2024-09-02 15:05:54
回复(0)
public ListNode deleteDuplicates (ListNode head) {
if(head == null || head.next == null) return head;
ListNode pre = head,last = head.next;
while(last != null){
if(pre.val == last.val){
pre.next = last.next;
last = pre.next;
}else{
last = last.next;
pre = pre.next;
}
}
return head;
}
发表于 2024-08-20 11:36:22
回复(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
// 算法的时间复杂度O(N)，额外空间复杂度O(1)
// 1.处理特殊链表
if (head == null || head.next == null) {
// 对于空链表，单结点链表，直接返回head
return head;
}
// 2.遍历链表，每次定位重复结点的最后一个结点，跳过中间结点
ListNode cur = head;
ListNode dupEnd = null;
while (cur != null) {
// 对于任一cur结点，哪怕没有重复，dupEnd至少是cur自己
dupEnd = cur;
while(dupEnd.next != null && dupEnd.val == dupEnd.next.val) {
// 如果发现重复，dupEnd往后移动一位
dupEnd = dupEnd.next;
}
// 循环结束时，dupEnd指向重复结点的最后一个，且不会是null
// 跳连 + 移动
cur.next = dupEnd.next;
cur = cur.next;
}
// 3.返回头部
return head;
}
}
发表于 2024-07-27 12:40:27
回复(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 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)
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)
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)
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)
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)
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)
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)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @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)
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)
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)
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)
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)
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)
问题信息
难度：
88条回答
424收藏
27794浏览
通过挑战的用户
查看代码-
2023-02-17 11:10:24 -
2022-10-24 16:13:01 -
2022-09-22 11:14:29
-
2022-09-19 21:20:13
-
2022-09-17 09:23:55
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
