刘晓锋

昨天 23:58 已编辑黑龙江八一农垦大学 C++ 发布于黑龙江

关注

链表（C++）

链表的基本概念：

链表是一种常见的基本数据结构，和数组一样属于线性表，但是与数组不同。链表不需要连续的内存位置来存储。

链表是一种动态的数据结构，由节点组成，每一个节点包含一个数据域和指针域。用数据域存储元素，指针域存储指向下一个节点的地址，以此形成链表。

1.节点结构：

每个节点通常包含两个部分：

1.数据域：

用来存储实际的数据（比如整数、字符串等等）。

2.指针域：

用来指向下一个节点的指针。

在双向链表中，节点还包含一个指向前节点的指针。

2.头节点：

链表的第一个节点，指向链表的起始位置。头节点一般不存储数据，但持有指向起始节点的指针。

通过头节点可以遍历链表。

3.尾节点：

链表的最后一个节点，其指针域通常指向nullptr（在C++中表示空指针），表示链表的结束。

4.链表的种类：

单向链表：每个节点只指向下一个节点，遍历只能从头到尾。

双向链表：每个节点有两个指针，一个指针指向上一个节点，一个指针指向下一个节点，支持双向遍历。

循环链表：最后一个节点的指针指向头节点，形成一个环，可以从任意节点开始遍历。

5.链表的优缺点：

优点：

1.动态内存分配：链表可以根据需求动态分配内存，无需预先分配固定大小的空间。因此链表在处理不确定数据规模时非常灵活。

2.高效的插入和删除：链表在进行插入和删除时，只需要调整指针的指向，无需移动其他元素。

缺点：

1.随机访问效率低：链表不支持通过索引直接访问元素，只能从头开始遍历。

2.额外的内存开销：每个节点不仅要存储数据，还要存储指向下一个节点的指针，增加了内存的使用量。

链表的基本操作：

动态创建链表的常用方法有两种：

头插入法：在链表的头部插入新的节点，新节点的指针域存储的指针指向原头节点，更新头节点为新节点。

尾插入法：在链表的尾部插入新的节点，将链表的最后一个节点的指针域存储的指针指向新节点。

1.单向链表：

创建节点：

struct Node{
  int value;//信息域
  Node* next;//指针域
};

头插入法创建链表：

struct Node{
  int value;
  Node* next;
};

void CreateNodeList(Node* head,int n){
  head->next=NULL;//单链表特性，最后一个节点的指针指向nullptr
  Node* p;//创建节点，用于记录新节点的地址
  for(int i=1;i<=n;i++){
	p=new Node;
	cin>>p->value;//输入指针域的数据
	p->next=head->next;//新节点和原虚头节点后面的节点连接
	head->next=p;//构建虚头节点和新节点的连接，以此来更新虚头节点
	}
}

int main(){
  Node* head=new Node;//创建一个虚头节点，用于记录第一节点的地址
  int n;//表示要插入的节点个数
  cin>>n;
  CreateNodeList(head,n);
  Node* p=head->next;//创建一个节点，让其为第一个节点
}

尾插入法创建链表：

struct Node{
  int value;
  Node* next;
};

void CreateNodeList(Node* head,int n){
  head->next=NULL;
  Node* p;//用于记录新节点的位置
  Node* q=head;//用于记录最后一个节点的位置
  for(int i=1;i<=n;i++){
	p=new Node;
	cin>>p->value;
	p->next=NULL;//新节点的指针指向nullptr
	q->next=p;//将最后一个节点的指针指向新节点的地址
	q=p;//更新最后一个节点的位置
  }
}

int main(){
  Node* head=new Node;
  int n;
  cin>>n;
  CreateNodeList(head,n);
}

2.链表的遍历：

void printfNodeList(Node* head){
  if(head->next==NULL){
	return;
  }
  Node* p=head->next;
  while(p!=NULL){
	cout<<p->value<<endl;
	p=p->next;
  }
}

3.链表的查找：

通过序号查找节点，找到返回去，没找到返回0：

int find(Node* head,int n){
  if(head->next==NULL){
	return 0;
  }
  Node* p=head->next;
  int i=1;
  while(i<n&&p!=NULL){
	p=p->next;
	i++;
  }
  if(p==NULL){
	return 0;
  }
  return 1;
}

通过与value值比较，找到第一个相等的节点，没找到返回0，找到返回1：

int find(Node* head,int number){
  if(head->neext==NULL){
	return 0;
  }
  Node* p=head->next;
  while(p!=NULL&&p->value!=number){
	p=p->next;
  }
  if(p==NULL){
	return 0;
  }
  return 1;
}

查找链表中的倒数第k个节点(k为有效数据)：

Node* find(Node* head,int k){
  if(head->next==NULL){
	return head;
  }
  Node* fast=head;//快指针
  Node* slow=head;//慢指针
  while(k--){
	fast=fast->next;//让快指针移动k次
  }
  while(fast){//判断快指针是否为空，如果为空，此时的慢指针指向的节点就是要找的目标节点
	fast=fast->next;
	slow=slow->next;
  }
  return slow;
}

给定一个头节点，返回链表中的中间节点，如果有两个中间节点，则返回第一个中间节点：

Node* MiddleNode(Node* head){
  if(head->next==NULL||head==NULL){
	return head;
  }
  Node* fast=head;
  Node* slow=head;
  while(fast!=NULL&&fast->next!=NULL){//每次让快指针移动两次，慢指针移动一次，当不满足循环条件时，此时慢指针所在的节点就是中间节点或者是中间节点的第一个节点
	fast=fast->next->next;
	slow=slwo->next;
  }
  return slow;
}

4.合并连个有序的链表：

合并为一个升序：

Node* merge(Node* L1,Node L2){
  if(L1==NULL)return L2;
  if(L2==NULL)return L1;
  Node* NewList=NULL;//记录合并之后链表的第一个位置
  Node* L=NULL;//记录合并之后链表的最后一个位置
  Node* p1=L1;
  Node* p2=L2;
  while(p1!=NULL&&p2!=NULL){
	if(NewList==NULL){//当新节点为空时，将更小的值的节点作为头节点，也就是让NesList作为头节点
	  NewList=p1->value<=p2->value?p1:p2;
	  L=NewList;//同时更新尾节点的位置
	}
	else{//当新节点不为空时，让L也就是尾节点指向比较之后的更小的节点
	  L->next=p1->value<=p2->value?p1:p2;
	  L=L->next;//同时更新尾节点的位置
	}
	if(p1->value<=p2->value){//移动p1的位置
	  p1=p1->next;
	}
	else{//移动p2的位置
	  p2=p2->next;
	}
  }
  if(p1==NULL){//当p1为空，也就是遍历完L1时，那么让尾节点指向L2上的剩余节点的第一个节点
	L->next=p2;
  }
  if(p2==NULL){//当p2为空，也就是遍历完L2时，那么让尾节点指向L1上的剩余节点的第一个节点
	L->next=p1;
  }
  return NesList;
}

5.删除操作：

找到目标节点删除，失败返回0，成功返回1：

int DeleteNode(Node* head,int n){
  if(head->next==NULL){
	return 0;
  }
  Node* p=head->next;//快指针
  Node* q=head;//慢指针
  int i=1;
  while(i<n&&p!=NULL){
	p=p->next;//移动快指针
	q=q->next;//移动慢指针
	i++;
  }
  if(p==NULL){//当快指针为空，遍历完成
	return 0;
  }
  q->next=p->next;//慢指针指向的节点的指针指向快指针指向的节点的指针指向的地址
  delete p;//删除目标节点
  return 1;
}

删除第一个值为目标值的节点，失败返回0，成功返回1：

int DeleteNode(Node* head,int number){
  if(head->next==NULL){
	return 0;
  }
  Node* p=head->next;
  Node* q=head;
  while(p!=NULL&&p->value!=number){
	q=q->next;
	p=p->next;
  }
  if(p==NULL){
	return 0;
  }
  q->next=p->next;
  delete p;
  return 1;
}

删除单链表中所有值为目标值的节点：

void DeleteNode(Node* head,int number){
  if(head->next==NULL){
	return;
  }
  Node* p=head->next;//快指针
  Node* q=head;//慢指针
  while(p!=NULL){//判断快指针是否为空
	if(p->value==number){//判断是否为目标节点
	  q->next=p->next;//慢指针指向的节点的指针指向快指针指向的节点的指针指向的地址
	  delete p;//删除目标节点
	  p=q->next;//更新快指针的位置
	}
	else{
	  p=p->next;//移动快指针
	  q=q->next;//移动慢指针
	}
  }
}

删除单链表中的所有重复值的节点：

void DeleteNode(Node* head){
  if(head->next==NULL){
	return;
  }
  Node* p=head->next;
  while(p!=NULL){//遍历链表
	Node* fast=p->next;//快指针
	Node* slow=p;//慢指针
	while(fast){//判断快指针是否为空，如果为空则链表完成遍历，一次只能删一个重复节点
	  if(fast->value==slow->value){//判断快慢指针的数据域存储的数据是否相等
		slow->next=fast->value;
		delete fast;
		fast=slow->next;
	  }
	  else{
		fast=fast->next;//移动快指针
		slow=slow->next;//移动慢指针
	  }
	}
	p=p->next;
  }
}

删除链表的倒数第n个节点，返回头节点：

Node* DeleteFind(Node* head,int n){
  Node* p=new Node;//虚头节点
  p->next=head;//记录头节点的位置
  Node* fast=head;
  Node* slow=head;//用慢指针记录目标节点
  Node* f=p;//f和slow始终差一步，记录目标节点的直接前驱
  while(fast!=NULL&&n--){//让快指针移动n次
	fast=fast->next;
  }
  while(fast){
	fast=fast->next;
	slow=slow->next;
	f=f->next;
  }
  f->next=slow->next;
  delete slow;
  return p->next;
}

删除排序链表中的重复元素，给点已排序的链表的头节点：

Node* DeleteNodeList(Node* head){
  if(head==NULL){
	return NULL;
  }
  Node* p=new Node;
  p->next=head;
  Node* f=p;
  while(f->next!=NULL&&f->next->next!=NULL){
	if(f->next->value===f->next->next->value){
	  int x=f->next->value;//记录需要删除节点的数据域的数据
	  while(f->next!=NULL&&f->next==x){//从f指针指向的节点开始遍历链表
		Node* t=f->next;//存储目标节点的直接前驱
		f->next=f->next->next;
		delete t;
	  }
	}
	else{
	  f=f->next;
	}
  }
  return p->next;
}

6.反转链表：

给定头节点，返回反转后的链表：

Node* ReverseList(Node* head){
  if(head==NULL||head->next==NULL){//基线条件
	return head;
  }
  //递归条件
  Node* newlist=ReverseList(head->next);
  head->next->next=head;
  head->next=NULL;
  return newlist;
}

双向链表：

创建节点：

struct DulNode(){
  int vlaue;
  DulNode* prior;//存放节点的直接前驱
  DulNode* next;//存放节点的直接后继
};

1.双向链表的构建：

1.插入时仅仅指出节点的直接前驱节点，构建链表时必须注意先后次序，先右后左。

s->next=p->next;//让s节点的next指针域指向p的直接后继节点
p->next->ptior=s;//让p的直接后继节点的prior指针域指向s
p->next=s;//断开p与之前的直接后继节点的连接，让p的next指针域指向s
s->prior=p;//让s的prior指针域指向p
如果先连接p会导致p的直接后继节点的位置丢失

2.插入时同时指出直接前驱和直接后继节点，插入时无需注意先后次序。

p->next=s;
s->prior=p;
s->next=q;
q->prior=s;

头插入法：

void CreateDulNodeList(DulNode* head,int n){
  head->next=NULL;
  head->prior=NULL;//初始化
  DulNode* p=new DulNode;
  cin>>p->value;
  p->next=NULL;
  p->prior=head;
  head->next=p;
  for(int i=2;i<=n;i++){
	p=new DulNode;
	cin>>p->value;
	head->next->prior=p;
	p->next=head->next;
	head->next=p;
	p->prior=head;
  }
}

尾插入法：

void CreateDulNodeList(DulNode* head,int n){
  head->next=NULL;
  head->prior=NULL;
  DulNode* p;
  DulNode* s=head;
  for(int i=1;i<=n;i++){
	p=new DulNode;
	cin>>p->value;
	p->next=NULL;
	p->prior=s;
	s->next=p;
	s=p;
  }
}

2.双向链表的节点删除：

设要删除的节点为p,删除时可以不引入新的辅助指针变量，可以直接先断链，再释放节点
p->prior->next=p->next;
p->next->prior=p->prior;//需要改变直接前驱节点的next指针域指向和直接后继节点的prior指针域的指向
delete p;

循环链表：

任意一个节点出发都可以找到链表中的其他节点，处理更加灵活方便

1.单向循环链表：每个节点有一个指向直接后继的指针域，尾节点的指针域的指针指向头节点。

2.双向循环链表：每个节点都有一个指向直接后继节点的指针域和指向直接前驱节点指针域，头节点的prior指针域指向尾节点，尾节点的next指针域指向头节点。

1.单向循环链表：

1.判断是否为循环链表：

思路：设定一个快指针和一个慢指针，让快慢指针按照设定的速度移动，如果链表为环形链表，则快指针一定会在某个时间点追上慢指针，所以当快慢指针指向的节点相同时，则为环形链表。如果当快指针移动到NULL，那么证明链表的尾节点的指针域的指针未指向头节点的地址，则不为环形链表。

给定一个头节点，判断是否有环，没有返回false，有返回true：

bool judge(Node* head){
  if(head==NULL||head->next==NULL){
	return false;
  }
  Node* fast=head->next;//快指针
  Node* slow=head;//慢指针
  while(slow!=fast){//当快慢指针指向的节点相同时，证明为一个环形链表
	if(fast!=NULL&&fast->next!=NULL){
	  fast=fast->next->next;;
	  slow=slow->next;
	}
	else{
	  return false;
	}
	return true;
  }
}

2.循环链表的操作：

对于单循环链表，除链表的合并外，其他的操作和单链表基本一致。

判断是否为空链表：

head->next=head;//当头节点的指针域的指针指向头节点本身则为空链表

head=nullptr;//判断头节点是否为空

判断是否是链表的尾节点：

p->next=head->next;//当节点的指针域的指针指向头节点就是尾节点
可以定义一个哨兵节点，让其指向头节点，一但某一节点的指针域的指针指向哨兵节点就为尾节点

头插入法：

void CreateNodeList(Node* head,int n){
  head->next=head;//初始化
  Node* p;
  p=new Node;//创建一个节点
  cin>>p->value;
  p->next=p;//让自己指向自己形成一个环
  head->next=p;//标记头节点的位置
  Node* t=p;//记录尾节点
  for(int i=2;i<=n;i++){
	p=new Node;
	cin>>p->value;
	p->next=head->next;//新节点的指针域的指针指向头节点
	head->next=p;//更新标记头节点的位置
	t->next=p;//让最后一个节点的指针域指向头节点
  }
}

尾插入法：

void CreateNodeList(Node* head,int n){
  head->next=head;//初始化
  Node* p=new Node;
  cin>>p->value;
  head->next=p;
  p->next=p;
  Node* s=p;//记录最后一个节点位置
  for(int i=2;i<=n;i++){
	p=new Node;
	cin>>p->value;
	s->enxt=p;//让最后一个节点的指针域的指针指向新节点
	p->next=head->next;//新节点的指针域的指针指向头节点
	s=p;//更新最后一个节点的位置
  }
}

2.双向循环链表：

1.创建节点：

struct DulNode(){
  int value;
  DulNode* prior;
  DulNode* next;
};

2.双向循环链表的构建：

头插入法：

void CreateDulNode(DulNode* head,int n){
  head->next=NULL;
  head->prior=NULL;//初始化虚头节点
  DulNode* p=new DulNode;
  cin>>p->value;
  p->next=p;
  p->prior=p;
  head->next=p;
  DulNode* s=p;//记录刚插入的第一个节点位置
  for(int i=2;i<=n;i++){
	p=new DulNode;
	cin>>p->value;
	p->next=head->next;
	head->next->prior=p;
	head->next=p;
	p->prior=s;
	s->next=p;
  }
}

尾插入法：

void CreateDulNode(DulNode* head,int n){
  head->next=NULL;
  head->prior=NULL;
  DulNode* p=new DulNode;
  cin>>p->value;
  p->next=p;
  p->prior=p;
  head->next=p;
  DulNode* s=p;
  for(int i=2;i<=n;i++){
	p=new DulNode;
	cin>>p->value;
	p->next=head->next;
	head->next->prior=p;
	s->next=p;
	p->prior=s;
	s=p;
  }
}