链表的反转
迭代方法的实现
图片引用于 https://zhuanlan.zhihu.com/p/48405334
- /**
- * Definition for singly-linked list.
- * struct ListNode {
- * int val;
- * ListNode *next;
- * ListNode(int x) : val(x), next(NULL) {}
- * };
- */
- class Solution {
- public:
- ListNode* reverseList(ListNode* head) {
- ListNode *curPe = NULL;
- ListNode *cur = head;
- ListNode *curNe;
- while(cur!=NULL)
- {
- curNe = cur->next;
- cur->next = curPe;
- curPe = cur;
- cur = curNe;
- }
- return curPe;
- //curpe cur curNe 三个指针一直保持着这个次序, 最后当 cur 指向 NULL 时, 结束. 反转后的头节点为 curPe.
- }
- };
递归方法实现
- /**
- * Definition for singly-linked list.
- * struct ListNode {
- * int val;
- * ListNode *next;
- * ListNode(int x) : val(x), next(NULL) {}
- * };
- */
- class Solution {
- public:
- ListNode* reverseList(ListNode* head) {
- if(head==NULL||head->next==NULL)
- return head;
- ListNode *p = reverseList(head->next);
- head->next->next =head;
- head->next =NULL;
- return p;
- }
- };
油管解释比较清楚的视频 https://www.youtube.com/watch?v=O0By4Zq0OFc
来源: http://www.bubuko.com/infodetail-3110203.html