面试算法 牛客题目 删除有序链表中重复的元素__she001的博客-爱代码爱编程

1.题目：  删除有序链表中重复的元素

描述
删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次  重点有序 
例如：
给出的链表为1→1→2,返回1→2.
给出的链表为1→1→2→3→3,返回1→2→3.

数据范围：链表长度满足 1000≤n≤100，链表中任意节点的值满足 100∣val∣≤100
进阶：空间复杂度 O(1)，时间复杂度 O(n)

2.算法：暴力算法

3.算法思路：

当前节点的数据，与下一个节点的数据对比  ， 假如相同  ，  当前 节点连接 下一个节点的下一个节点  ， 当前节点 后面那个节点 销毁！

4.代码：

/*************************************************
作者：She001
时间:2022/10/3
题目：  删除有序链表中重复的元素-I
描述
删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次  重点有序 
例如：
给出的链表为1→1→2,返回1→2.
给出的链表为1→1→2→3→3,返回1→2→3.

数据范围：链表长度满足 1000≤n≤100，链表中任意节点的值满足 100∣val∣≤100
进阶：空间复杂度 O(1)，时间复杂度 O(n)



***************************************************/
//算法：
//1.暴力算法：数据有序  从大到小  


#include<bits/stdc++.h>
using namespace std;
typedef struct node
{
	int i;
	node *next;	
}; 


void print(node * head)//打印链表 
{
	node* pp= head;//复制头节点 
	while(pp!=NULL)//判断这个节点是否为空  链表是否结束 
	{
		cout<<pp->i<<"  ";
		pp=pp->next;//指向下一个 
	}
	cout<<endl;
	
}



int lianbiao_num(node * head)//函数的作用 返回链表的个数
{
	int i=0;
	node* pp=head;
	while(pp!=NULL)
	{
		i++;
		pp=pp->next;	
	}
	//cout<<"链表中节点的个数: "<<i<<endl;
	return i;	
} 


node * reverseList(node* head)//翻转链表 
{
	if(head==NULL)
	{
		return NULL;	
	}	
	node * a = head;
	node * b = NULL;
	while(a!=NULL)
	{
		node * c = a->next;
		a->next=b;
		b=a;
		a=c;
	}
	return b;	
} 


//1.暴力算法：
//
node *  fangfa_1(node * head)
{
	if(head==NULL ||  head->next==NULL)//假如链表为空  或者只有一个节点  那么我们直接返回头节点 
	{
		return head;
	}
	node * k1= head;
	while(k1!=NULL  &&  k1->next!=NULL)//遍历节点 
	{
		if((k1->i)==(k1->next->i))//判断数据是相同 
		{
			node * kk=k1->next;//记录节点 
			k1->next=k1->next->next;//建立连接 
			k1=k1->next;//数据相同   节点 变为下一个的下一个 
			delete kk;//释放节点 
		}	
		else
		{
			k1=k1->next;//遍历下一个节点 
		}
	}
	return head;
}





int main()
{
	
	
	//建立  第一个 单链表  
	node *a1=new node;
	node *a2=new node;
	node *a3=new node;
	node *a4=new node;
	node *a5=new node;
	node *a6=new node;
	node *a7=new node;
	node *a8=new node;
	node *a9=new node; 
	
	a1->i=1;//链表节点的复制 
	a2->i=1;
	a3->i=2;
	a4->i=3;
	a5->i=4;
	a6->i=4;
	a7->i=5;
	a8->i=6;
	a9->i=6;
	
	
	a1->next=a2;//链表的连接 
	a2->next=a3;
	a3->next=a4;
	a4->next=a5;
	a5->next=a6;
	a6->next=a7;
	a7->next=a8;
	a8->next=a9;//a5 是 两个链表的节点 
	a9->next=NULL;
	

	node * k1= fangfa_1(a1);
	print(k1);
	
	
	return 	0;
}