Leetcode 206. Reverse Linked List

2019-11-10 18:32:06

字體：大中小

供稿：網(wǎng)友

Reverse a singly linked list. Hint: A linked list can be reversed either iteratively or recursively. Could you implement both?

s思路： 1. 要求iterative和recursive. 2. 先來(lái)iterative。iterative寫過(guò)幾次了，簡(jiǎn)單的就是用dummy,然后PRe,pnow,pnext三個(gè)指針不停移動(dòng)，交換！寫完發(fā)現(xiàn)，dummy都省了，直接三個(gè)指針移位和交換就搞定了！ 3. 再來(lái)recursive: 這里寫圖片描述 x需要注意的是：代碼寫完后，檢查在結(jié)尾的地方，也就是鏈表兩頭是否因?yàn)樯倭藢?duì)指針清零等操作導(dǎo)致的cycle。如上圖，就是1->2之間的指針沒(méi)有清零，而2->1又建立起來(lái)，于是cycle!

//方法1：iterative.搞了半天，居然都不用加dummy。直接返回尾指針！class Solution {public: ListNode* reverseList(ListNode* head) { /*ListNode node(0); ListNode* dummy=&node; dummy->next=head;*/ ListNode* pre=NULL,*pnow=head,*pnext=NULL; while(pnow){ pnext=pnow->next; pnow->next=pre; if(!pnext) return pnow; pre=pnow; pnow=pnext; } return NULL; }};//方法2：recursive:class Solution {public: ListNode* reverseList(ListNode* head) { if(!head) return NULL; if(!head->next) return head; ListNode* tail=head->next; ListNode* newhead=reverseList(head->next); tail->next=head; head->next=NULL;//bug:沒(méi)有這一句，就cycle.加上這一句，就cycle free return newhead; }};

上一篇：win10 uwp 如何拖動(dòng)一個(gè)TextBlock的文字到另一個(gè)TextBlock

下一篇：5.1數(shù)組的定義&5.2數(shù)組的順序表示和實(shí)現(xiàn)