Reverse Link List Recursion

Reverse a linked list using recursion.

Example :
Given 1->2->3->4->5->NULL,

return 5->4->3->2->1->NULL.

Solution:

Time: O(n)
Space: O(1)

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     public int val;
 *     public ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
public class Solution {
    // 1->2->3->4->5
    // 1<-2<-3<-4<-5
    public ListNode reverseList(ListNode A) {
        if (A == null || A.next == null) return A;
        ListNode newHead = reverseList(A.next);
        A.next.next = A;
        A.next = null;
        return newHead;
    }
}