How to recursively reverse a Linked List?

Technology CommunityCategory: Linked ListsHow to recursively reverse a Linked List?
VietMX Staff asked 1 year 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->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) {
    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);
    }
}