时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
题目描述
输入一个链表，反转链表后，输出新链表的表头。
思路：
一、先遍历链表中的每一个元素，并依次放入vector容器中，然后再反序存入链表中
/* 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; } vector<int> elem; ListNode *tmp = pHead; while(tmp) { elem.push_back(tmp->val); tmp = tmp->next; } reverse(elem.begin(),elem.end()); int i = 0; tmp = pHead; while(tmp) { tmp->val = elem[i]; tmp = tmp->next; i++; } return pHead; } };
二、设立指针currPoint当前地址，prePoint是指当前指针的前一个节点，newPOint指新链表的头指针，之所以在设立指针nextPoint是为了在链断开之前储存后面的地址信息
/* 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 *prePoint=NULL; ListNode *currPoint=pHead; ListNode *newPoint = NULL; while(currPoint) { ListNode *nextPoint = currPoint->next; if(nextPoint==NULL)//当nextPoint为空时，说明当前节点为尾结点 newPoint = currPoint; currPoint->next = prePoint;//指针反转 prePoint = currPoint; currPoint = nextPoint; } return newPoint; } };
三、采用递归的方法，这种方法非常巧妙，它利用了递归走到链表的尾端，然后再更新每一个节点next的指向，实现链表的反转。
/* 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; //先反转后面的链表，走到链表的末端结点 ListNode *reverseNode = ReverseList(pHead->next); //再将当前节点设置为后面节点的后续节点 pHead->next->next = pHead; pHead->next = NULL; return reverseNode; } };
原文链接: https://www.cnblogs.com/whiteBear/p/12500968.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/335546
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
