# How to recursively reverse a Linked List?

VietMX Staff asked 1 year ago

• 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;

1->2->3->4->5

Now assume that the last node has been reversed. Just like this:

1->2->3->4<-5

And 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) {
}
}