思路一：利用栈的后进先出
创新互联主要从事成都网站设计、成都网站建设、外贸网站建设、网页设计、企业做网站、公司建网站等业务。立足成都服务松滋,十载网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:13518219792
代码：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead)
{
//利用栈的后进先出的特点，最后进的最先出
stack s1;
ListNode *p=pHead;
//将链表中的每个元素的值进行压栈
while(p!=NULL)
{
s1.push(p->val);
p=p->next;
}
//出栈，并且将栈顶元素放入链表中
p=pHead;
while(!s1.empty())
{
p->val=s1.top();
s1.pop();
p=p->next;
}
return pHead;
}
}; 思路二：进行摘结点，然后头插
代码：
class Solution {
public:
ListNode* ReverseList(ListNode* pHead)
{
if(pHead==NULL)
{
return NULL;
}
ListNode *newHead=NULL;
ListNode *cur=pHead;
ListNode *tmp=NULL;
while(cur!=NULL)
{
tmp=cur;
//关键点：一定要让cur先往后走,再进行插入操作
//不然会让原链表找不到后面的结点，结果就会变成只有一个结点
cur=cur->next;
tmp->next=newHead;
newHead=tmp;
}
return newHead;
}
};思路三：利用递归，找到最后一个结点作为函数的返回值，然后在改变该链表的每一个当前pHead的位置
代码：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead)
{
//终止条件
if(pHead==NULL||pHead->next==NULL)
{
return pHead;
}
//newHead得到对应的返回值，尾节点
ListNode *newHead=ReverseList(pHead->next);
//然后将当先栈帧中的pHead的next进行更改
//比如说1->2->3->4->NULL
//newHead->4
//pHead->3
//4->3->null
//此时指向3的还有1->2->3->null
pHead->next->next=pHead;
pHead->next=NULL;
return newHead;
}
};
