链表反转是数据结构中的经典问题，本文给出的主要有迭代法、递归法、栈操作法三种实现方式来实现链表反转。

一、链表基础结构定义

struct Node {

    int data;    // 节点存储的数据

    Node* let;  // 指向下一个节点的指针,名字也可以叫next，叫什么无所谓

};



Node* head = nullptr; // 链表头指针（初始为空）

通过结构体定义了一个链表节点（Node），每个节点包括整型的data和一个指针类型的next指针，用来存储下一个节点的地址。并初始化头节点，将head指针的指向设置为null（也可以说是0）。

因为嫌麻烦，比较懒。实现的流程图就选择手绘，不美观但是实用。

因为bro编关于这类代码就是看着下面的流程图写的。

方法1：迭代法

思路：

通过三个指针（current、prev、next）逐个反转节点间的指向关系，逐步将链表方向倒置。

Node* ReverseIterative() {

   

  Node* current,*prev,*cnext;

  current = head;

  Node* prev = nullptr;

  temp = head;



  while(current != nullptr){

   cnext = current ->let；//链表断开前用指针cnext存储下一个节点的当前地址值

   current ->let = prev;//prev是反转后链表temp的前一个节点的指针

   prev = current;//prev右移

   current = cnext;//current右移

  }

  head = prev;

  return head; 

}

实现逻辑如下图：

方法2：递归法

思路：

利用递归的栈特性，从链表尾部开始逐层反转节点指向，最终将整个链表方向倒置。

打印链表：

打印链表也可以实现链表的反转

void reversePrint(Node* p){

 if(p == NULL){//在NULL前一直会递归调用，一直到NULL都执行Print(p->next);然后输出的值是反过来的

  cout << "/n" << endl;

  return;

 }

//打印的反转或者不反转，其实区别在于下面两条语句的顺序

Print(p->next);//在stack区

 cout << p->data << endl;

 } 

如下图所示（RP为reversePrint函数）

递归实现一个链表的反转

void ReversePrint(Node* p){

 if(p->next == NULL){//递归退出条件

  head = p;

  return;

 }

 ReversePrint(p->next);//达到退出条件前，一直执行ReversePrint(p->next);

 Node* q = p->next;//编号3  

 q->next = p;//这两行代码可以写成p->next ->next = p;

 p->next = NULL;

} 

递归方法2：

class Solution {

public:

    ListNode* reverseList(ListNode* head) {

        // 递归终止条件：空链表或单节点链表

        if (head == nullptr || head->next == nullptr) {

            return head;

        }

        // 递归反转后续链表，得到新头节点

        ListNode* newHead = reverseList(head->next);

        // 调整指针方向：将当前节点的下一个节点的next指向当前节点

        head->next->next = head;

        // 断开当前节点的原指向，防止循环，这个思路也可以用快慢指针似乎

        head->next = nullptr;

        // 返回新头节点

        return newHead;

    }

};

方法3：栈操作法

思路：

利用栈的后进先出（LIFO）特性，将链表节点依次压入栈中，再依次弹出并重新连接，即可实现反转。

void Reverse(){



 stack<Node*> S;//压入栈中的是指针，是地址

  stuct Node{

  int data;

  Node* next;

 } 

 

  Node *temp = S.top();//指向栈顶，当前最后一个节点的引用 

  head = temp;

  S.pop();

  while(!S.empty()){

  temp->next = S.top();

  S.pop();

  temp = temp->next;

 }

 temp->next = NULL;

 

}

如此就可以通过三种方式实现了链表的反转。

注：部分思路和代码参考了印度数据结构大神Harsha Suryanarayana的课程。

感兴趣的佬可以去看这位大神的网课，非常推荐。

或者觉得数据结构学得不好，学不懂的非常建议去看他的网课，绝对比学校的好，通俗易懂。

b站上面就有很多。

因为学一下还是有好处，锻炼一下您的脑子，让它比之前更聪明一点。

如有错误，欢迎指出！感谢您，因为代码不是最近写的。