Reverse a linked list.
Have you met this question in a real interview?
Yes
Example
For linked list 1->2->3
, the reversed linked list is 3->2->1
Challenge
Reverse it in-place and in one-pass
Tags Expand
Yes
For linked list
1->2->3
, the reversed linked list is 3->2->1
Reverse it in-place and in one-pass
Initial Solution:
Use three pointers and draw sketch:
Don't forget to add Null to head and reverse next and cur pointer after while loop
Time: O(n)
Space: O(1)
Use three pointers and draw sketch:
Don't forget to add Null to head and reverse next and cur pointer after while loop
Time: O(n)
Space: O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | /** * Definition of ListNode * * class ListNode { * public: * int val; * ListNode *next; * * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list. * @return: The new head of reversed linked list. */ ListNode *reverse(ListNode *head) { // write your code here ListNode *prev = head; if(!head) return NULL; ListNode *cur = prev->next; if(!cur) return head; head->next = NULL; ListNode *next = cur->next; while(next){ cur->next = prev; prev = cur; cur = next; next = next->next; } cur->next = prev; return cur; } }; |
Below two solutions all reference: http://algorithm.yuanbin.me/zh-cn/linked_list/reverse_linked_list.html
Solution 1: Exchange adjacent nodes
Two pointers solution: Set prev node as null is a convenient way to set head->next =NULL
Time: O(n)
Space: O(1)
Time: O(n)
Space: O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | /** * Definition of ListNode * * class ListNode { * public: * int val; * ListNode *next; * * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list. * @return: The new head of reversed linked list. */ ListNode *reverse(ListNode *head) { // write your code here ListNode* prev = NULL; ListNode* cur = head; while(cur){ ListNode* temp = cur->next; cur->next = prev; prev = cur; cur = temp; } return prev; } }; |
Solution 2: Recursion
Recursive nested layers: O(n)
Time: O(n)
space:O(1) ----without stack space
Recursive nested layers: O(n)
Time: O(n)
space:O(1) ----without stack space
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | /** * Definition of ListNode * * class ListNode { * public: * int val; * ListNode *next; * * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list * @return: The new head of reversed linked list. */ ListNode *reverse(ListNode *head) { // write your code here if(head == NULL) return head; if(head->next == NULL) return head; //keep tracking head of the reversed linkedlist ListNode *newHead = reverse(head -> next); head->next->next = head; head->next = NULL; return newHead; } }; |
Lintcode second:
Three pointers solution:
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: /** * @param head: The first node of linked list. * @return: The new head of reversed linked list. */ ListNode *reverse(ListNode *head) { // write your code here ListNode* prev, *cur, *next; prev = NULL; cur = head; if(!head) return NULL; next = cur->next; while(next){ cur->next = prev; prev = cur; cur = next; next = next->next; } cur->next = prev; return cur; } }; |
two pointers solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | class Solution { public: /** * @param head: The first node of linked list. * @return: The new head of reversed linked list. */ ListNode *reverse(ListNode *head) { // write your code here ListNode *prev, *cur; prev = NULL; cur = head; if(!head) return head; while(cur){ ListNode* next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; } }; |
没有评论:
发表评论