516 字
1 分钟
反转链表——迭代实现
反转链表
本篇文章我会继续带你用c/cpp实现链表的反转。
既然是做数据结构的题目，那么画图是必要的，这将使得逻辑变得更加清晰！
瞧瞧！多美美丽的手法！
那么如何做到反转链表呢？我们总不可能，将数据一一迁移，这样做实在太过麻烦！？🤔
那如何操作呢？
是啊！如何操作呢？
不改数据就去改链接嘛！
从上面变成了下面，简直浅显易懂！😎（ps:你知道画图有多累吗！？💢）
方法论
如何实现呢？
方法一：使用循环去修改节点连接，也就是迭代
方法二：使用递归
我们来用迭代实现，这样更容易理解一些！
代码实现
要实现反转，首先我们要遍历链表，操作如下。
#include<iostream>using namespace std;
struct Node { int data; Node* next;};Node* head;void Reverse(){ Node* temp; temp = head; while(temp!=NULL){ temp=temp->next; }}但是这样操作的话，我们只能知道下一个节点的位置，而无法知道上一个节点的位置，因此我们还需要一个临时变量！
我们稍作修改
void Reverse(){ Node *temp,*prev; temp = head; prev = NULL; while(temp!=NULL){ temp->next=prev;//我们将节点的next设置为previce，也就是上一个节点的地址 }}假设我们在操作第一个节点！
结果变成了这样，也就是说，我们成功的把第一个节点连接到了上一个节点，这里是NULL。
那么问题来了，我们如何前往下一个节点？🤔
好吧，这显然有问题，所以我们必须用一个临时变量存储下一个节点的位置！
因此我们继续改进
void Reverse(){ Node *next,*prev,*current; current=head; prev=NULL; while(current!=NULL){ next = current->next;//让next指向下一个节点 current->next=prev;//将本节点连接到上个节点 prev=current;//移动prev节点 current=next;//这里别忘了哦！移动当前节点到下一个节点。 }}
好啦，这样能顺利到达末尾，但是最后一个节点还需要修改！
Node *Reverse(){ Node *next,*prev,*current; current=head; prev=NULL; while(current!=NULL){ next = current->next; current->next=prev; prev=current; current=next;//这里别忘了哦！ } head=prev;//处理末尾连接 return head;//便于打印链表}这里加了返回值，并且重新定义了函数类型，便于打印！
完整代码实现
#include<iostream>using namespace std;
struct Node { int data; Node* next;};Node* head;void Print(){ Node *temp; temp = head; while(temp!=NULL){ cout<<temp->data; temp=temp->next; } cout<<"\n";}void Insert(int data){ Node *temp=new Node(); temp->data=data; temp->next=NULL; if(head==NULL){ head=temp; return; } Node *temp2=head; while(temp2->next!=NULL){ temp2=temp2->next; } temp2->next=temp;};Node *Reverse(Node *head){ Node *next,*prev,*current; current=head; prev=NULL; while(current!=NULL){ next = current->next; current->next=prev; prev=current; current=next;//这里别忘了哦！ } head=prev;//处理末尾连接 return head;//便于打印链表}int main(){ head = NULL; Insert(2); Insert(4); Insert(6); Insert(5); Print(); head = Reverse(head); Print(); return 0;}要点：我们的reverse函数里污染了head！！！！所以我们需要传入head进入这个函数！！！😎
部分信息可能已经过时