VietMX Staff asked 3 years ago
Start from the bottom up by asking and answering tiny questions:
- What is the reverse of
null(the empty list)?null. - What is the reverse of a one element list? the element.
- What is the reverse of an n element list? the reverse of the rest of the list followed by the first element.
P.S.
How to understand that part?
head.next.next = head;
head.next = null;Think about the origin link list:
1->2->3->4->5Now assume that the last node has been reversed. Just like this:
1->2->3->4<-5And this time you are at the node 3 , you want to change 3->4 to 3<-4 , means let 3->next->next = 3 (as 3->next is 4 and 4->next = 3 is to reverse it)
Complexity Analysis
Assume that n is the list’s length, the time complexity is O(n). The extra space comes from implicit stack space due to recursion. The recursion could go up to n levels deep then space complexity is O(n).
Implementation
var reverseList = function(head) {
if (!head) {
return head;
}
let pre = head.next;
head.next = null;
return fun(head, pre);
function fun(cur, pre) {
if (pre == null) {
return cur;
}
let tmp = pre.next;
pre.next = cur;
return fun(pre, tmp);
}
}