十年网站开发经验 + 多家企业客户 + 靠谱的建站团队
量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决
思路一:利用栈的后进先出
创新互联主要从事成都网站设计、成都网站建设、外贸网站建设、网页设计、企业做网站、公司建网站等业务。立足成都服务松滋,十载网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:13518219792
代码:
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* ReverseList(ListNode* pHead) { //利用栈的后进先出的特点,最后进的最先出 stacks1; 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; } };