LeetCode: Reverse Linked List

Two bad solutions, both are iterative
Solution 1: O(n), cannot pass test, need too much memory

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

class Solution { public: ListNode* reverseList(ListNode* head) { if(head==NULL) return NULL; if(head->next==NULL) return head; vector<ListNode*> Nodes; ListNode* cur=head; while(cur->next!=NULL){ Nodes.push_back(cur); } //ListNode* newhead; //newhead=cur; head=cur; while(Nodes.size()!=0){ cur->next=Nodes.back(); cur=Nodes.back(); Nodes.pop_back(); } cur->next=NULL; //return newhead; return head; } };

Solutions 2: O(n^2) speed is too low.
It took O(n) to get newest tail pointer in the input List which is unnecessary.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

class Solution { public: ListNode* reverseList(ListNode* head) { if(head==NULL) return NULL; //if(head->next==NULL) return head; ListNode* pre; ListNode* cur=head; for(cur=head;cur->next!=NULL;pre=cur,cur=cur->next); ListNode* newhead=cur; cur->next=pre; pre->next=NULL; while(pre!=head){ for(cur=head;cur->next!=NULL;pre=cur,cur=cur->next); cur->next=pre; pre->next=NULL; } return newhead; } };

Two final solutions:

Iterative Way:
Remember the point before current pointer, just reconnect from the beginning to the end of the linkedlist

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

class Solution { public: ListNode* reverseList(ListNode* head) { if(head==NULL) return NULL; //if(head->next==NULL) return head; ListNode* pre=NULL; ListNode* cur=head; while(cur!=NULL){ ListNode* nextNode=cur->next; cur->next=pre; pre=cur; cur=nextNode; } return pre; } };

Recursive way:


Reference:
http://articles.leetcode.com/2010/04/reversing-linked-list-iteratively-and.html