在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5
数据范围：链表长度满足 
，链表中的值满足 
进阶：空间复杂度 %5C)
，时间复杂度 %20%5C)
例如输入{1,2,3,3,4,4,5}时，对应的输出为{1,2,5}，对应的输入输出链表如下图所示：
[编程题]删除链表中重复的结点
0<=n<=1000，直接用容量1000的int数组统计全链表val出现的次数，最后遍历数组，只有是1的才创建节点，时间复杂度O(n)，空间复杂度O(1)
public ListNode deleteDuplication(ListNode pHead) {
int[] a = new int[1001];
while(pHead!=null){
a[pHead.val]++;
pHead = pHead.next;
}
ListNode head = null;
ListNode pre = null;
for(int val = 0;val<=1000;val++){
if(a[val] == 1){
if(head == null){
head = new ListNode(val);
pre = head;
}else{
pre.next = new ListNode(val);
pre = pre.next;
}
}
}
return head;
}
发表于 2024-11-29 12:33:00
回复(0)
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = pHead;
ListNode p = dummyHead;
ListNode q = dummyHead.next;
while (q != null && q.next != null) {
ListNode t = q.next;
if (q.val != t.val) {
p = q;
q = t;
} else {
while (t!=null && q.val == t.val) {
t = t.next;
}
p.next = t;
q = t;
}
}
return dummyHead.next;
}
}
发表于 2024-07-30 17:56:30
回复(0)
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
//设置虚拟节点
ListNode dummy = new ListNode(-1);
dummy.next = pHead;
//设置快慢指针
ListNode slow = dummy;
ListNode fast = pHead;
//用于判断是否出现重复节点
boolean flag = false;
//特殊情况单独处理
if(pHead == null){
return pHead;
}
while(fast.next != null){
//此时出现重复节点
while(fast.next != null && fast.val == fast.next.val){
flag = true;
fast = fast.next;
}
//此时slow后面全是重复的节点，全删掉
if(fast.next == null){
slow.next = null;
break;
}
fast = fast.next;
if(flag){
slow.next = fast;
flag = false;
}else{
slow = slow.next;
}
}
return dummy.next;
}
}
发表于 2023-11-20 17:09:31
回复(0)
//笨方法来啦
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
HashMap<Integer, Integer> map = new HashMap<>();
List<Integer> list = new ArrayList<>();
while (pHead != null) {
map.put(pHead.val, map.getOrDefault(pHead.val, 0) + 1);
list.add(pHead.val);
pHead = pHead.next;
}
ListNode newHead = new ListNode(-1);
ListNode cur = newHead;
for (Integer integer : list) {
if (map.get(integer) == 1){
cur.next = new ListNode(integer);
cur = cur.next;
}
}
return newHead.next;
}
}
发表于 2023-10-16 20:30:08
回复(0)
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
ListNode newHead = new ListNode(-1);
ListNode tmp = newHead;
ListNode cur = pHead;
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-09 17:29:30
回复(0)
使用pre记录与上一个节点值是否相同，如果当前节点与之前的与之后的都不同，加入结果链表。
public class Solution {
public ListNode deleteDuplication(ListNode head) {
ListNode res = new ListNode(0), cur = res;
boolean pre = true;
for(ListNode node = head; node != null; node=node.next){
if(node.next != null){
if(pre && node.val != node.next.val){
cur.next = node;
cur = cur.next;
}
pre = node.val !=node.next.val;
}else{
if(pre){
cur.next =node;
cur = cur.next;
}
}
}
cur.next = null;
return res.next;
}
}
发表于 2023-05-17 10:43:42
回复(0)
import java.util.HashSet;
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
if(pHead == null) return null;
HashSet<Integer> set = new HashSet<>();
HashSet del = new HashSet<>();
ListNode p = pHead;
while (p != null) {
if (set.contains(p.val)) {
del.add(p.val);
} else {
set.add(p.val);
}
p = p.next;
}
p = pHead;
while (del.contains(p.val)) {
p = p.next;
if(p == null) return null;
}
pHead = p;
ListNode q = p.next;
while (q != null) {
while (del.contains(q.val)) {
q = q.next;
if(q == null) break;
}
if(q == null) {
p.next = null;
break;
}
p.next = q;
p = q;
q = p.next;
}
return pHead;
}
}
发表于 2023-03-07 14:12:26
回复(0)
import java.util.LinkedHashMap;
import java.util.Set;
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
LinkedHashMap<Integer,Integer> linkedHashMap = new LinkedHashMap<>();
ListNode ans = new ListNode(-1);
ListNode p = pHead;
ListNode a = ans;
while(p!=null){
if(linkedHashMap.containsKey(p.val)){
linkedHashMap.put(p.val,linkedHashMap.get(p.val)+1);
}else{
linkedHashMap.put(p.val,1);
}
p = p.next;
}
Set<Integer> set = linkedHashMap.keySet();
for (Integer i:set){
if(linkedHashMap.get(i)==1){
a.next = new ListNode(i);
a = a.next;
}
}
return ans.next;
}
}
发表于 2022-11-12 00:03:19
回复(0)
满足进阶时空复杂度的解法
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
if(pHead==null) return null;
int[] a=new int[1000]; //a数组用于记录每个结点值出现的次数
for(int i=0;i<1000;i++) a[i]=0;
ListNode p=pHead;
while(p!=null){ //遍历一遍链表 统计每个值出现的次数
a[p.val]++;
p=p.next;
}
p=pHead;
ListNode q=pHead.next;
if(q==null) return pHead;
while(q!=null){ //利用p和q在整个链表中删除重复节点
if(a[q.val]>1){
p.next=q.next;
q=p.next;
}
else{
p=p.next;
q=q.next;
}
}
if(a[pHead.val]>1) pHead=pHead.next; //最后判断一下头节点需不需要删
return pHead;
}
}
发表于 2022-10-11 20:07:36
回复(0)
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
/**
解题思路：
1.首先遍历一遍节点，记录下那些要删除的节点，然后第二次遍历一一删除
*/
public class Solution {
private HashMap<Integer,Integer> map=new HashMap<>();
public ListNode deleteDuplication(ListNode pHead) {
ListNode temp=pHead;
while(temp!=null){
int val=temp.val;
if(map.containsKey(val)){
map.put(val,map.get(val)+1);
}else{
map.put(val,1);
}
temp=temp.next;
}
//第二次遍历进行删除
ListNode target;
while(pHead !=null && map.get(pHead.val)>1) pHead=pHead.next;
target=pHead;
temp=target;
while(temp!=null && temp.next!=null){
if(map.get(temp.next.val)>1){
//需要删除
temp.next=temp.next.next;
}else{
temp=temp.next;
}
}
return target;
}
}
发表于 2022-08-10 11:28:36
回复(0)
import java.util.*;
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
if (pHead == null) return null;
ListNode p = new ListNode(-1);
p.next = pHead;
Set<Integer> set = new HashSet<>();
Set<Integer> duplicateSet = new HashSet<>();
ListNode l = p.next;
while (l != null) {
if (set.contains(l.val)) {
duplicateSet.add(l.val);
} else {
set.add(l.val);
}
l = l.next;
}
ListNode slow = p;
ListNode fast = p.next;
while (fast != null) {
if (duplicateSet.contains(fast.val)) {
fast = fast.next;
} else {
slow.next = fast;
slow = slow.next;
fast = fast.next;
}
}
slow.next = null;
return p.next;
}
}
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
if (pHead == null) return null;
ListNode p = new ListNode(-1);
p.next = pHead;
Set<Integer> set = new HashSet<>();
Set<Integer> duplicateSet = new HashSet<>();
ListNode l = p.next;
while (l != null) {
if (set.contains(l.val)) {
duplicateSet.add(l.val);
} else {
set.add(l.val);
}
l = l.next;
}
ListNode slow = p;
ListNode fast = p.next;
while (fast != null) {
if (duplicateSet.contains(fast.val)) {
fast = fast.next;
} else {
slow.next = fast;
slow = slow.next;
fast = fast.next;
}
}
slow.next = null;
return p.next;
}
}
发表于 2022-06-07 22:28:51
回复(0)
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
if (pHead == null) {
return null;
}
ListNode newHead = new ListNode(0);
newHead.next = pHead;
ListNode prev = newHead;
ListNode last = pHead;
while (last != null) {
//节点不重复;prev跟last都向前走一步;直至链表尾
while (last.next != null && last.val != last.next.val) {
prev = prev.next;
last = last.next;
}
//节点重复;last走到不重复处停下来或者走到链表尾停下来
while (last.next != null && last.val == last.next.val) {
last = last.next;
}
//走到这里结果一共有三种,注意：prev永远指向的是前驱有效起始节点：
// 1. last.next != null 并且 (prev, last] 限定了一段重复范围，此时进行去重
// 2. last.next == null && (prev, last] 限定了一段重复范围，此时进行去重，最后相当于prev- >next = nullptr
// 3. last.next == null && prev.next == last,这说明，从本次循环开始，大家都不相同，就不需 要进行去重，这个是特殊情况
if (prev.next != last) {
prev.next = last.next;
}
last = last.next;
}
return newHead.next;
}
}
发表于 2022-05-26 11:09:35
回复(0)
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
if(pHead==null){
return null;
}
ListNode newHead=new ListNode(-1);
newHead.next=pHead;
ListNode cur=newHead;
ListNode slow=pHead;
ListNode fast=pHead.next;
while(fast!=null){
if(slow.val!=fast.val){
cur=slow;
slow=fast;
fast=fast.next;
}else{
while(fast!=null&&slow.val==fast.val){
fast=fast.next;
}
cur.next=fast;
if(cur.next!=null){
slow=fast;
fast=fast.next;
}
}
}
return newHead.next;
}
}
发表于 2022-05-09 15:40:13
回复(0)
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
//哈希
if(pHead == null) return null;
int[] arr = new int[1010];
//cur代表要删除的节点
//prev代表要删除节点的前驱
ListNode prev = pHead;
ListNode cur = pHead.next;
while(prev != null) {
//填充数组中的元素
arr[prev.val]++;
prev = prev.next;
}
prev = pHead;
while(cur != null) {
if(arr[cur.val] > 1) {
prev.next = cur.next;
cur = cur.next;
} else {
prev = cur;
cur = cur.next;
}
}
//最后处理头节点
if(arr[pHead.val] > 1) {
pHead = pHead.next;
}
return pHead;
}
}
用哈希来做，单链表删除的核心思想：找到要删除节点的前一个节点
发表于 2022-05-08 17:23:45
回复(0)
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
ListNode pre = null;//由于删除 所以必须有前面一个节点
ListNode p = pHead;
while(p != null && p.next != null){
if(p.val == p.next.val){
ListNode q = p.next;
while(q.next != null && q.val == q.next.val){
q = q.next;
}
p = q.next;
//代表前面全是重复的或者是接连的成对重复，但是后面还有节点
if(pre == null && p != null){
pHead = p;
}
//代表前面全是重复的或者是接连的成对重复，而且后面没有节点了
else if(pre == null && p == null){
return null;
}
//pre有走过，直接删除
else{
pre.next = p;
}
}else{
pre = p;
p = p.next;
}
}
return pHead;
}
}
发表于 2022-04-05 22:32:56
回复(0)
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
if(pHead == null || pHead.next == null) return pHead;
ListNode root = new ListNode(-1);
root.next = pHead;
ListNode pre = root ;
ListNode cur = root ;
while(cur!=null){
while( cur.next!=null&&cur.val == cur.next.val) cur=cur.next;
// cur.next!=null && cur.val == cur.next.val
cur=cur.next;
if(cur!=null&&cur.next!=null&&cur.val == cur.next.val) continue;
pre.next = cur;
pre = pre.next;
}
return root.next;
}
}
发表于 2022-03-24 10:16:53
回复(0)
public ListNode deleteDuplication(ListNode pHead) {
if (pHead == null) return null;
ListNode head = new ListNode(0), p;
head.next = pHead;
p = head;
while (p.next != null && p.next.next != null) {
if (p.next.val == p.next.next.val) {
ListNode tmp = p;
while (tmp.next != null && tmp.next.next != null && tmp.next.val == tmp.next.next.val) {
tmp = tmp.next;
}
p.next = tmp.next.next;
} else{
p = p.next;
}
}
return head.next;
}
发表于 2022-03-14 23:35:05
回复(0)
首先例子举的不好，两个连续的段放到一起属于特殊的，应该举个一般的，如1 2 3 3 4 5这种。可以把基本逻辑写出来。
首结点也可能会被删掉，所以使用添加一个辅助首结点来处理这种情况，最后只需要返回newHead.next就行，省心。
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
if(pHead == null) return null;
ListNode head = new ListNode(0);
head.next = pHead;
ListNode p1 = head, p2 = pHead;
while(p2 != null){
if(p2.next != null && p2.val == p2.next.val){
while(p2.next != null && p2.val == p2.next.val){
p2 = p2.next;
}
p1.next = p2.next;
p2 = p2.next;
}else{
p1 = p1.next;
p2 = p2.next;
}
}
return head.next;
}
}
发表于 2022-03-07 16:38:16
回复(0)
问题信息
难度：
190条回答
2689收藏
149187浏览
通过挑战的用户
查看代码-
2023-03-14 00:52:25 -
2023-03-08 18:59:35 -
2023-02-13 21:51:56 -
2022-11-12 17:37:39 -
2022-11-11 16:42:44
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
