思路一：利用栈的后进先出
代码：
计算
安全
数据库
网络和加速
企业服务
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead)
{
//利用栈的后进先出的特点，最后进的最先出
stack<int> 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;
}
};亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
