206. Reverse Linked List
Given the head of a singly linked list, reverse the list, and return the reversed list.
Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?
- iterative solution
- 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
|
class Solution { public: ListNode* reverseList(ListNode* head) { if(!head) return head; ListNode *cur = head, *prev = NULL, *tmp; while(cur) { tmp = cur->next; cur->next = prev; prev = cur; cur = tmp; } return prev; } };
|
- recursive solution
- 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
|
class Solution { ListNode* solution(ListNode* parent, ListNode* child) { if(!child) return parent; ListNode* res = solution(child, child->next); child->next = parent; parent->next = NULL; return res; } public: ListNode* reverseList(ListNode* head) { return !head ? head : solution(head, head->next); } };
|