给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为
, 返回
.
给出的链表为
, 返回
.
例如：
给出的链表为
给出的链表为
数据范围：链表长度 
，链表中的值满足 
要求：空间复杂度 )
，时间复杂度
进阶：空间复杂度 )
，时间复杂度
[编程题]删除有序链表中重复的元素-II
struct ListNode* deleteDuplicates(struct ListNode* head ) {
// write code here
if(head == NULL || head->next == NULL)//链表为空或者只有一个，直接返回
{
return head;
}
struct ListNode*h = NULL;//创建一个新单链表，这是头节点
struct ListNode*t = NULL;//尾结点
struct ListNode*pnew = NULL;//新结点
struct ListNode*p = head;
while(p)
{
if(p->next!=NULL && p->val == p->next->val)
{
while(p->next != NULL && p->val == p->next->val)//用while找到所有相同的数
{
p = p->next;
}
p = p->next；//往下走一步，所有相同的都没有获取
}
else if(p->val != p->next->val)//获取不同的数
{
struct ListNode* pnew = malloc (sizeof(struct ListNode));
pnew->val = p->val;
pnew->next = NULL;
if(h == NULL)//从无到有
{
h = pnew;
t = pnew;
}
else//尾插
{
t->next = pnew;
t = pnew;
}
p = p->next;
}
}
return h;
}
发表于 2022-07-23 13:58:37
回复(0)
我的思路就是两个指针遍历，一个指针作为头结点，用t记录前一个结点的值，相等就跳过，不等就接上头结点，链表的最后一个元素由于fast到空指针会跳过，循环出来再判别要不要接上。
struct ListNode* deleteDuplicates(struct ListNode* head ) {
// write code here
if(head==NULL)
return head;
struct ListNode*slow=head,*fast=head->next;
struct ListNode*p1=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode*p2=p1;
int t=-1001;
while(fast){
if(slow->val==fast->val||slow->val==t){
t=slow->val;
slow=slow->next;
fast=fast->next;
}
else{
p1->next=slow;
p1=p1->next;
slow=slow->next;
fast=fast->next;
t=p1->val;
}
}
if(slow->val!=t){
p1->next=slow;
p1=p1->next;
}
p1->next=NULL;
return p2->next;
}
// write code here
if(head==NULL)
return head;
struct ListNode*slow=head,*fast=head->next;
struct ListNode*p1=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode*p2=p1;
int t=-1001;
while(fast){
if(slow->val==fast->val||slow->val==t){
t=slow->val;
slow=slow->next;
fast=fast->next;
}
else{
p1->next=slow;
p1=p1->next;
slow=slow->next;
fast=fast->next;
t=p1->val;
}
}
if(slow->val!=t){
p1->next=slow;
p1=p1->next;
}
p1->next=NULL;
return p2->next;
}
发表于 2022-05-24 20:16:40
回复(0)
通过字典完成对数据频次的统计，然后生成链表
############# Methond 1 ##############
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param head ListNode类
# @return ListNode类
#
# from collections import defaultdict
class Solution:
def deleteDuplicates(self , head: ListNode) -> ListNode:
# 判断空链表和单值链表
if (not head)&nbs***bsp;(not head.next):
return head
# 通过列表生成链表
l = []
cur = head
while cur:
l.append(cur.val)
cur = cur.next
## 初试化字典
v = 0
dic = {k:v for k in l}
## 统计数值的频次
for i in l:
dic[i] += 1
## 生成新的列表。这里已经去除了多次出现的数据
l = []
for k, v in dic.items():
if v <= 1:
l.append(k)
# 通过列表生成链表
res = head = ListNode(0) ## 设置头结点，省去了条件判断
for i in range(0, len(l)):
res.next = ListNode(l[i])
res = res.next
return head.next
优化：
class ListNode: def __init__(self, x): self.val = x self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param head ListNode类 # @return ListNode类 # # from collections import defaultdict class Solution: def deleteDuplicates(self , head: ListNode) -> ListNode: # write code here # 判断空链表和单值链表 if (not head)&nbs***bsp;(not head.next): return head # 通过列表生成链表 l = [] cur = head while cur: l.append(cur.val) cur = cur.next ## 初试化 带有频次的字典 import collections dic = collections.Counter(l) ## 列表生成式 l = [k for k,v in dic.items() if v <= 1] # 通过列表生成链表 res = head = ListNode(0) ## 设置头结点，省去了条件判断 for i in range(0, len(l)): res.next = ListNode(l[i]) res = res.next return head.next
发表于 2022-04-10 10:19:12
回复(1)
C 语言写的：
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
typedef struct ListNode Node;
struct ListNode* deleteDuplicates(struct ListNode* head ) {
// write code here
if(head == NULL || head->next == NULL)
{
return head;
}
Node *pre = NULL;
Node *mid = head;
Node *cur = mid->next;
//开头重复
if(mid->val == cur->val)
{
while(cur && mid->val == cur->val)
{
//每次循环释放mid结点
Node *p3 = mid;
mid = cur;
cur = cur->next;
free(p3);
if( !cur)
{
return NULL;
}
}
//释放cur结点前一个的mid结点
Node *p4 = mid;
pre = cur;
mid = cur->next;
if(cur->next == NULL)
{
cur = NULL;
}
else
{
cur = cur->next->next;
}
printf("%d ",pre->val);
head = pre;
free(p4);
}
//中间重复
while(cur)
{
//如果删除后的首结点还重复，继续删除
while(1)
{
//如果头结点和第二个结点重复，则删除，一直删到不重复为止
if(pre->val == mid->val && pre )
{
while(cur && pre->val == mid->val)
{
Node *p5 = pre;
pre = mid;
mid = cur;
cur = cur->next;
free(p5);
}
//各结点后移
Node *p6 = pre;
pre = mid;
mid = cur;
//如果cur不为空。则cur后移
if(cur)
{
cur = cur->next;
}
free(p6);
head = pre;
}
else
{
break;
}
}
//到这一步说明前面的已经没有重复了，只存在中间重复或者末尾重复
if(mid->val == cur->val && mid != cur)
{
Node *p1 = cur;
cur = cur->next;
free(p1);
//结尾重复
//如果cur为空，直接让pre指向空，并释放mid结点和cur结点
if(!cur)
{
pre->next = NULL;
free(mid);
free(cur);
return head;
}
//如果cur的值不等于mid的值并且cur不为空，则cur后移，并同时删除mid结点
if(cur->val != mid->val && cur)
{
Node *p2 = mid;
mid = cur;
cur = cur->next;
free(p2);
}
//此时mid结点的值已经不等于cur结点的值，直接让pre结点指向mid结点，让链表连接起来
pre->next = mid;
}
else
{
//都不相等，直接后移
pre = mid;
mid = cur;
cur = cur->next;
}
}
return head;
}
发表于 2022-03-13 19:42:21
回复(0)
class Solution:
def deleteDuplicates(self , head: ListNode) -> ListNode:
if head is None:
return head
dummyhead = ListNode(0)
dummyhead.next = head
cur = dummyhead
pre = cur # 记录重复元素的前一位指针
flag = 0 # 重复标志位
while cur.next :
cur = cur.next # 向前走一步
while cur.next and cur.next.val == cur.val: # 判断重复
flag = 1
cur = cur.next
if flag == 1:
pre.next = cur.next # 去重
flag = 0
else:
pre = cur
return dummyhead.next
发表于 2022-03-08 12:27:08
回复(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) {
if (head == null) return null;
ListNode dummy = new ListNode(-1), curr = head, start = dummy;
dummy.next = head;
while (curr.next != null) {
if (curr.val != curr.next.val) {
curr = curr.next;
start = start.next;
continue;
}
while (curr.next != null && curr.val == curr.next.val) {
curr = curr.next;
}
if (curr.next == null) {
start.next = null;
break;
}
curr = curr.next;
start.next = curr;
}
return dummy.next;
}
}
发表于 2021-12-16 20:51:40
回复(0)
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null) return head;
ListNode realHead = new ListNode(-1);
realHead.next = head;
ListNode fast = head;
ListNode slow = realHead;
while(fast!=null && fast.next!=null)
{
if(fast.next!=null && fast.val == fast.next.val)
{
while(fast.next!=null && fast.val == fast.next.val)
{
fast = fast.next;
}
slow.next = fast.next;
fast = fast.next;
}
else
{
fast = fast.next;
slow = slow.next;
}
}
return realHead.next;
}
}
发表于 2021-06-15 09:42:28
回复(0)
其实这一题可以在上一题的基础上加一点东西，上一题是删除相同，只保留一个，那么我们可以分为两步，第一步：删除相同，保留一个；第二步：删除那一个。
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
if(head == NULL || head->next == NULL)
return head;
ListNode preHead(0);
preHead.next = head;
ListNode *preNow = &preHead;
ListNode *now = head;
ListNode *pre = head,*p = head->next;
int flag = 0;
while(now != NULL)
{
while(p != NULL)
{
if(p->val == now->val)
{
pre->next = p->next;
delete p;
p = pre->next;
flag++;
}
else
{
pre = p;
p = pre->next;
}
}
if(flag)
{
preNow->next = now->next;
delete now;
now = preNow->next;
pre = now;
if(pre != NULL)
p = pre->next;
flag = 0;
}
else
{
preNow = now;
now = now->next;
pre = now;
if(pre != NULL)
p = pre->next;
}
}
head = &preHead;
head = head->next;
return head;
}
};
发表于 2019-07-31 14:12:22
回复(0)
//两种写法，递归和非递归
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
//非递归
/*
if(!head || !head->next){
return head;
}
ListNode *root = new ListNode(head->val-1);
root->next = head;
ListNode *pre = root;
ListNode *cur = head;
while(cur && cur->next){
if(cur->val != cur->next->val){
pre = cur;
}else{
while(cur->next!=NULL && cur->val == cur->next->val){
cur = cur->next;
}
pre->next = cur->next;
}
cur = cur->next;
}
return root->next;
*/
//递归
if(!head || !head->next){
return head;
}
ListNode *root = new ListNode(head->val - 1);
root->next = head;
ListNode *cur = head;
if(cur->next && cur->val != cur->next->val){
cur->next = deleteDuplicates(cur->next);
return cur;
}else{
int tmp = cur->val;
while(cur->next && cur->next->val == tmp){
cur = cur->next;
if(!cur){
return NULL;
}
}
return deleteDuplicates(cur->next);
}
}
};
发表于 2019-06-24 09:55:20
回复(0)
//思路很简单，就是记录val值相同的节点个数，有多个的话只修改前一个不重复节点的后继节点
//只有一个的话就将前一个不重复节点向后移
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
if(head == NULL)
return NULL;
ListNode *L = new ListNode(0);
L->next = head;
ListNode *p,*q,*tmp;
p = L;
q = head;
int count;
while(q!=NULL)
{
count = 0;
tmp = q;
while(q!=NULL && q->val==tmp->val)
{
count++;
q = q->next;
}
if(count>1)
{
p->next = q;
}else if(count==1){
p->next = tmp;
p = p->next;
}
}
p->next = NULL;
return L->next;
}
};
发表于 2019-01-08 21:02:12
回复(0)
思路：使用一个虚节点作为头结点来保存结果。最后返回虚节点的next。使用指针p遍历链表，遇到p.next.val != p.val时认为不是重复结点，加入结果链表，或遇到尾节点时也加入。若遇到重复结点全部删除后继续处理。
最后需要注意的是将结果链表的尾节点的next设置为null，防止和其他结点相连。
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0),pNewList = dummy;
ListNode p = head;
while(p != null) {
if(p.next == null || p.val != p.next.val) {
pNewList.next = p;
pNewList = p;
p = p.next;
} else {
int sameVal = p.val;
for(p = p.next; p != null && p.val == sameVal; p = p.next)
;
}
}
pNewList.next = null;
return dummy.next;
}
编辑于 2018-12-07 12:24:26
回复(0)
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
if(head == NULL || head->next == NULL)
return head;
ListNode *L = new ListNode(-1);
L->next = head;
ListNode *p = L;
ListNode *q = L->next;
while(q)
{
while(q->next && q->next->val == q->val)
q = q->next;
if(p->next != q)
{
ListNode *t = q->next;
q->next = NULL;
p->next = t;
q = t;
}else{
p = q;
q = q->next;
}
}
return L->next;
}
};
发表于 2017-08-29 01:07:42
回复(0)
分享一个IDE直接可用的
#include <iostream>
using namespace std;
struct ListNode
{
ListNode *next;
int val;
};
ListNode* CreateListNode(int value)
{
ListNode* pNode = new ListNode();
pNode->val = value;
pNode->next = NULL;
return pNode;
}
void ConnectListNodes(ListNode* pCurrent, ListNode* pNext)
{
if (pCurrent == NULL)
{
printf("Error to connect two nodes.\n");
exit(1);
}
pCurrent->next = pNext;
}
void PrintList(ListNode* pHead)
{
printf("PrintList starts.\n");
ListNode* pNode = pHead;
while (pNode != NULL)
{
printf("%d\t", pNode->val);
pNode = pNode->next;
}
printf("\nPrintList ends.\n");
}
ListNode *DeleteDuplicateNode(ListNode *pHead)
{
if (pHead == NULL)
return NULL;
ListNode* dummy = CreateListNode(0);
dummy->next = pHead;
ListNode* Pre = dummy;
ListNode* Cur = pHead;
while (Cur != NULL)
{
while (Cur->next != NULL&&Cur->val == Cur->next->val)
Cur = Cur->next;
if (Pre->next == Cur)
{
Pre = Pre->next;
Cur = Cur->next;
}
else
{
Pre->next = Cur->next;
Cur = Cur->next;
}
}
return dummy->next;
}
void main()
{
ListNode* pNode1 = CreateListNode(1);
ListNode* pNode2 = CreateListNode(1);
ListNode* pNode3 = CreateListNode(2);
ListNode* pNode4 = CreateListNode(2);
ListNode* pNode5 = CreateListNode(4);
//ListNode* pNode6 = CreateListNode(4);
//ListNode* pNode7 = CreateListNode(5);
ConnectListNodes(pNode1, pNode2);
ConnectListNodes(pNode2, pNode3);
ConnectListNodes(pNode3, pNode4);
ConnectListNodes(pNode4, pNode5);
//ConnectListNodes(pNode5, pNode6);
//ConnectListNodes(pNode6, pNode7);
ListNode *zkd = DeleteDuplicateNode(pNode1);
PrintList(zkd);
}
发表于 2017-08-02 20:59:10
回复(0)
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head)
{
ListNode *fake= new ListNode(0);
fake->next = head;
ListNode *p = fake;
while(head)
{
if(head->next && head->next->val == head->val)
{
ListNode *temp=head->next;
while(temp->next && temp->next->val == head->val)
temp=temp->next;
head = temp;
p->next = temp->next;
}
else
{
p->next = head;
p = p->next;
}
head = head->next;
}
return fake->next;
}
};
发表于 2017-07-18 16:18:53
回复(0)
class Solution {
public:
ListNode *deleteDuplicates(ListNode *pHead) {
if (pHead == NULL || pHead->next == NULL) return pHead;
ListNode* head = new ListNode(INT_MIN);
head->next = pHead;
ListNode* p = head;
ListNode* q = head->next;
while(q) {
while(q->next && q->next->val == q->val) q = q->next;
if(p->next != q) {
ListNode* tmp = q->next;
q->next = NULL; //将重复结点断开
p->next = tmp;
q = tmp;
}
else {
p = q;
q = q->next;
}
}
return head->next;
}
};
发表于 2017-03-10 17:30:03
回复(0)
public class Solution {
public static ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null) return head;
ListNode newHead = new ListNode(0);
newHead.next = head;
ListNode pre = newHead;
ListNode cur = head;
while (cur != null && cur.next != null) {
if(cur.val != cur.next.val) pre = cur;
else {
while (cur.next != null && cur.val == cur.next.val)
cur = cur.next;
pre.next = cur.next;
}
cur = cur.next;
}
return newHead.next;
}
}
发表于 2016-11-17 22:18:01
回复(0)
// 思路：当前节点值跟上个节点和下个节点都不重复的时候，就是符合要求的
function deleteDuplicates( head ) {
// write code here
let newHead = null
let newPre = null
let cur = head
let preVal = null
while (cur) {
const next = cur.next
if (cur.val !== preVal && (!next || next.val !== cur.val)) {
const node = {
val: cur.val,
next: null
}
if (newPre === null) {
newHead = node
newPre = node
} else {
newPre.next = node
newPre = node
}
}
preVal = cur.val
cur = next
}
return newHead
}
发表于 2021-11-18 16:38:10
回复(0)
// 删节点
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
if(head == NULL || head->next == NULL) return head;
ListNode *pre = new ListNode(666);
pre->next = head;
ListNode *p = pre, *q;
while(p->next && p->next->next) {
if(p->next->val == p->next->next->val) {
q = p->next->next->next;
while(q && q->val == p->next->val) q = q->next;
p->next = q;
} else {
p = p->next;
}
}
return pre->next;
}
};
发表于 2017-10-07 16:46:18
回复(0)
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
ListNode *beforehead = new ListNode(0);
ListNode *cur = beforehead;
ListNode *p = head;
ListNode *q = head;
beforehead->next = head;
while (p){
while (q!=NULL && q->val == p->val){
q = q->next;
}
//检查以p为起点的元素到已q结束的位置的元素中是否有重复元素
if (p->next == q){
cur = p;
p = q;
}
else{
p = q;
cur->next = q;
}
}
return beforehead->next;
}
};
发表于 2016-05-19 09:52:48
回复(0)
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head==null||head.next==null)
return head;
ListNode newHead = new ListNode(head.val-1);
newHead.next = head;
ListNode cur = head;
ListNode last = newHead;
while(cur!=null&&cur.next!=null){
if(cur.val!=cur.next.val){
last = cur;
}else{
while(cur.next!=null&&cur.val==cur.next.val)
cur = cur.next;
last.next = cur.next;
}
cur = cur.next;
}
return newHead.next;
}
}
发表于 2016-06-03 19:25:39
回复(5)
问题信息
难度：
385条回答
1259收藏
26275浏览
通过挑战的用户
查看代码-
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号
