Leetcode 206. Reverse Linked List

2019-11-09 20:55:11

字體：大中小

來源：轉載

供稿：網友

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. 先來iterative。iterative寫過幾次了，簡單的就是用dummy,然后PRe,pnow,pnext三個指針不停移動，交換！寫完發現，dummy都省了，直接三個指針移位和交換就搞定了！ 3. 再來recursive: 這里寫圖片描述 x需要注意的是：代碼寫完后，檢查在結尾的地方，也就是鏈表兩頭是否因為少了對指針清零等操作導致的cycle。如上圖，就是1->2之間的指針沒有清零，而2->1又建立起來，于是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:沒有這一句，就cycle.加上這一句，就cycle free return newhead; }};

上一篇：poj1961

下一篇：SPOJ 694&&705