在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5
数据范围：链表长度满足 
，链表中的值满足 
进阶：空间复杂度 %5C)
，时间复杂度 %20%5C)
例如输入{1,2,3,3,4,4,5}时，对应的输出为{1,2,5}，对应的输入输出链表如下图所示：
[编程题]删除链表中重复的结点
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)
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
//这种需要返回新的头结点题目，需要创建一个虚拟的头节点，让虚拟节点连接原来的头结点
//删除所有重复的节点，那么就需要一个前驱节点去记录最后一个没有重复的节点，然后一个cur去遍历链表，
// 遇到重复的就跳过，找到不重复的就把上次最后一个不重复的节点的后继连接到下一个不重复的节点，
// 如果后面还有重复的，那么就再把不重复节点的后继连接到下一个没有重复的节点
ListNode newHead = new ListNode(0);//虚拟节点
newHead.next=pHead;
ListNode prev=newHead;//前驱节点，记录不重复节点位置
ListNode cur=pHead;//搜索待删除节点
//遍历链表
while (cur!=null){
//如果当前节点值不等于下一个节点的值
if(cur.next==null || cur.val!=cur.next.val){ //cur.next==null保证在遍历到最后一个节点时，此时cur在最后一个节点，就需要让cur为空，才能跳出循环，所以要加上cur==null这个条件
//那么就不用删，往后走
prev=prev.next;
cur = cur.next;
}else{
//如果当前节点的值等于下一个节点的值，就要找到不重复的下一个节点
while(cur.next!=null && cur.val==cur.next.val){
//让它继续遍历，直到找到不重复节点为止
cur = cur.next;
}
//找到了下一个不重复的节点，但是prev不着急跳过来，因为prev位置必须是不重复节点，但是此时还不一定当前节点是不重复的，所以需要先判断
//可以先把前驱节点的后继连接过来，但是前驱节点没那么快过来
//此时找到了一个不重复节点，说明当前节点的下一个节点是不重复的，可以把前驱节点的后继连过来
prev.next = cur.next;
//继续搜索待删除节点
cur = cur.next;
}
}
return newHead.next;//虚拟节点的下一个节点就是新链表头结点
}
}
发表于 2022-02-13 11:41:56
回复(0)
问题信息
难度：
188条回答
2597收藏
143435浏览
通过挑战的用户
查看代码-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
