206. Reverse Linked List

← Back to problem

Approach 2: Recursive

The recursive version is slightly trickier and the key is to work backwards. Assume that the rest of the list had already been reversed, now how do I reverse the front part? Let's assume the list is: n₁ → … → n_k-1 → n_k → n_k+1 → … → n_m → Ø

Assume from node n_k+1 to nm had been reversed and you are at node n_k.

n₁ → … → n_k-1 → n_k → n_k+1 ← … ← n_m

We want n_k+1’s next node to point to nk.

So,

n_k.next.next = n_k;

Be very careful that n1's next must point to Ø. If you forget about this, your linked list has a cycle in it. This bug could be caught if you test your code with a linked list of size 2.

Implementation

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

Complexity Analysis

• Time complexity : ${O}(n)$. Assume that $n$ is the list's length, the time complexity is ${O}(n)$.
• Space complexity : ${O}(n)$. The extra space comes from implicit stack space due to recursion. The recursion could go up to $n$ levels deep.