1.问题
输入一个链表，反转链表后，输出新链表。(题目来自牛客网，文章代码在牛客网中实现，使用语言C++）
2.知识点梳理
（1）节点的结构
(2)栈：后进先出；所以在递归函数栈内，按照后进先出的顺序
3.思路和代码
方法一：非递归
# 思路
首先：
相当于：
然后：
最后：
# 代码
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ /* 方式一：非递归 */ class Solution { public: ListNode* ReverseList(ListNode* pHead) { // 定义三个指针 // 当前指针 ListNode *Pnow = pHead; // 当前节点的后继指针 ListNode *Pnext = NULL; // 当前节点的前驱指针 ListNode *Ppre = NULL; // 定义尾指针为空 ListNode *tail = NULL; // 循环遍历指针 while(Pnow!=NULL){ // 下一个指针 Pnext = Pnow->next; // 如果Pnext为空，则找到了尾指针 if(NULL == Pnext){ tail = Pnext; } // 反转链表，下一节点指向当前指针的前驱 Pnow->next = Ppre; // 处理断链的情况，使用pre指针保存当前节点的状态 Ppre = Pnow; // 当前节点后移一位 Pnow = Pnext; } return Ppre; } };
方法二：递归
前面非递归方式是从前面数1开始往后依次处理，而递归方式则恰恰相反，它先循环找到最后面指向的数5，然后从5开始处理依次翻转整个链表
# 思路
首先：
指针H迭代到底如下图所示，并且设置一个新的指针作为翻转后的链表的头。由于整个链表翻转之后的头就是最后一个数，所以整个过程NewH指针一直指向存放5的地址空间
（过程：程序刚开始执行，if 语句失效，进入 else 语句，然后执行Node *NewH = reverseList(H->next);第二个结点的指针参数传入递归函数，一直到，最后一个结点的指针参数传入递归函数，if 语句有效H->next == NULL，返回当前的H 给 NewH 指针指向）
然后：
由于在递归函数栈内，按照后进先出的顺序，反转链表操作从末尾节点开始一直到节点1
（过程：将H指向的地址赋值给H->next->next指针，并且一定要记得让H->next =NULL，也就是断开现在指针的链接，否则新的链表形成了环，下一层H->next->next赋值的时候会覆盖后续的值）
最后：
所有节点反转成功
代码：
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ /* 方法二：递归 */ class Solution { public: ListNode* ReverseList(ListNode* H) { // 链表为空或者链表只有一个值或者递归到最后一个节点 if(H == NULL || H->next == NULL){ return H; } // 先递归走到链表的末端结点,返回当前的H 给 NewH 指针指向 ListNode* NewH = ReverseList(H->next); // 再反转链表（后进先出） //将H指向的地址赋值给H->next->next指针 H->next->next = H; // 一定要记得让H->next =NULL H->next = NULL; return NewH; } };
4.参考文章：
https://www.cnblogs.com/kubixuesheng/p/4394509.html