C++数据结构与算法之反转链表的方法详解

2023-09-25 20:35:06 52

本文实例讲述了C++数据结构与算法之反转链表的方法。分享给大家供大家参考，具体如下：

算法概述：要求实现将一条单向链表反转并考虑时间复杂度。

算法分析：

数组法(略)：

将列表元素逐个保存进数组，之后再逆向重建列表
点评：实现逻辑最简单，需要额外的内存开销。

移动指针：

通过三个指针逐个从链表头开始逐一反转链表元素的指针
点评：不需要额外的内存开销，会改变原始链表。

递归：

以递归的方式首先找到链表尾部，再逐一反转指针
点评：不需要额外的内存开销，不会改变原始链表。

算法实现：

构建链表结构

/*节点结构*/
structNODE
{
intdata;
structNODE*next;
};
/*添加元素-压栈*/
voidpush(NODE**head,intdat){
structNODE*new_node=newNODE();
new_node->data=dat;
new_node->next=*head;
*head=new_node;
}
/*添加元素-添加*/
voidadd(NODE**head,intdat){
structNODE*new_node=newNODE();
new_node->data=dat;
new_node->next=NULL;
if(*head!=NULL){
structNODE*temp=*head;
while(temp->next!=NULL){
temp=temp->next;
}
temp->next=new_node;
}
else{
*head=new_node;
}
}

移动指针

/*反转列表*/
voidreverse(NODE**head){
structNODE*pre=NULL;
structNODE*cur=*head;
structNODE*nxt;
while(cur!=NULL){
//反转指针
nxt=cur->next;
cur->next=pre;
//移动指针
pre=cur;
cur=nxt;
}
*head=pre;
}

递归

/*反转列表-复制原表返回反转表*/
NODE*reverse(NODE*head){
if(head==NULL||head->next==NULL){
returnhead;
}
NODE*new_head=reverse(head->next);
//反转指针
head->next->next=head;
head->next=NULL;
returnnew_head;
}

打印链表

/*打印队列*/
voidprint(NODE*head){
NODE*temp=head;
while(temp!=NULL){
std::cout<data<next;
}
}

完整代码如下：

#include
/*节点结构*/
structNODE
{
intdata;
structNODE*next;
};
/*添加元素-压栈*/
voidpush(NODE**head,intdat){
structNODE*new_node=newNODE();
new_node->data=dat;
new_node->next=*head;
*head=new_node;
}
/*添加元素-添加*/
voidadd(NODE**head,intdat){
structNODE*new_node=newNODE();
new_node->data=dat;
new_node->next=NULL;
if(*head!=NULL){
structNODE*temp=*head;
while(temp->next!=NULL){
temp=temp->next;
}
temp->next=new_node;
}
else{
*head=new_node;
}
}
/*反转列表*/
voidreverse(NODE**head){
structNODE*pre=NULL;
structNODE*cur=*head;
structNODE*nxt;
while(cur!=NULL){
//反转指针
nxt=cur->next;
cur->next=pre;
//移动指针
pre=cur;
cur=nxt;
}
*head=pre;
}
/*反转列表-复制原表返回反转表*/
NODE*reverse(NODE*head){
if(head==NULL||head->next==NULL){
returnhead;
}
NODE*new_head=reverse(head->next);
//反转指针
head->next->next=head;
head->next=NULL;
returnnew_head;
}
/*打印队列*/
voidprint(NODE*head){
NODE*temp=head;
while(temp!=NULL){
std::cout<data<next;
}
}
intmain(){
structNODE*n=NULL;
add(&n,1);
add(&n,2);
add(&n,3);
n=reverse(n);
print(n);
return0;
}

希望本文所述对大家C++程序设计有所帮助。

C++数据结构与算法之反转链表的方法详解

热门推荐

随机推荐