题目描述
输入一个链表，反转链表后，输出新链表的表头。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
通过的代码： 修改链表的结构
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead)
{
if(pHead==NULL) return NULL;//注意程序鲁棒性
ListNode* pNode=pHead;//当前指针 每次都指向当前的结点
ListNode* pReverseHead=NULL;//新链表的头指针
ListNode* pPrev=NULL;//当前指针的前一个结点
while(pNode!=NULL){//当前结点不为空时才执行
//目的是为了逐个的向后移动结点 赋给新的链表pNext。此链表会越来越短
ListNode* pNext=pNode->next;//链断开之前一定要保存断开位置后边的结点
if(pNext==NULL)//当pNext为空时，说明当前结点为尾节点
pReverseHead=pNode;//为了最后输出尾结点
//指针反转过程
pNode->next=pPrev; //当前结点的下一个指向为之前保留的上一个结点 相当于由后指向前 但不用担心的是
//后面结点的连接情况已经保存
pPrev=pNode; // pPrev更新为当前结点,以便下一次操作
pNode=pNext;//结点向后移动
}
return pReverseHead;
}
};
原来：1->2->3
反转：1<-2<-3
反转的思路：1、定义一个暂存结点 ，目的是暂存上一个结点
2、定义一个链表B每次存放链表A下一个结点后面的子链表
3、将当前结点指向上一个结点
循环操作即可
注意的事项是：相当于是原链表上执行反转操作 ，不过还定义了一个存放子链表的链表B
最后输出反转后的头结点
特殊情况是：当结点为空则返回NULL
递归的方法实现
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
//如果链表为空或者链表中只有一个元素
if(pHead==NULL||pHead->next==NULL) return pHead;
//先反转后面的链表，走到链表的末端结点
ListNode* pReverseNode=ReverseList(pHead->next);
//再将当前节点设置为后面节点的后续节点
pHead->next->next=pHead;
pHead->next=NULL;
return pReverseNode;//每次执行到返回的pReverseNode还没有执行，相当于压栈中，
}
};
参考：https://www.nowcoder.com/profile/4162969/codeBookDetail?submissionId=15921939
从倒数第二个递归开始执行后面的语句：pHead->next->next=pHead; pHead->next=NULL;
换种方式描述是：pHead是递归函数的参数，是当前要处理的节点，对应链表的倒数第二个节点指针，pHead->next是最后一个 节点的指针，命名为lastNode，（lastNode）->next = pHead，pHead->next = NULL
从倒数第二个递归开始节点指针依次出栈，每次修改当前节点的下一个节点指向自己，然后自己指向空指针，一直到当前节点为第一个结点firstNode，(firstNode->next)->next = firstNode, firstNode->next = nullptr。
理解：相当于实现倒数第一个结点指向倒数第二个结点。然后递归，倒数第2指向倒数第三个结点。最后实现链表反转。相当于出栈
