Quali sono le complessità temporali e spaziali di questo metodo ricorsivo che inverte una lista concatenata?

Quali sono le complessità di tempo e spazio di questo metodo Java che inverte un elenco collegato singolarmente (di lunghezza n)?

Sono più interessato a conoscere il ragionamento alla base della complessità dello spazio. Fammi sapere se desideri che fornisca LinkedListNodeSingly e un'applet di convenienza.

Credo che qui sia la complessità spaziale che quella temporale siano O(n) . Il tempo è O(n) poiché andiamo alla coda e lavoriamo all'indietro attraverso ciascuno dei nodi n . Non sono sicuro che lo spazio sia O(n) perché anche se creiamo new_head per ogni fotogramma, ci accingiamo a puntarlo su un nodo esistente (partendo dal caso base) e lo passiamo sopra. Pertanto, sebbene creiamo riferimenti n , tutti puntano alla stessa posizione che contiene un valore. Quindi, lo spazio O(1) anche nel caso in cui eseguiamo LinkedListNodeSingly new_head = null; e 'restituisci new_head'?

/**
 * Inspired by: http://www.programmerinterview.com/index.php/data-structures/reverse-a-linked-list/
 * 
 * Time: O(n), at least I think so, since it is recursive, going through each node once for list of size n
 * Space: O(1), if we don't use a return val, but since we do, each frame would create new_head once, for O(n)
 */
public static LinkedListNodeSingly reverseUsingRecursion(LinkedListNodeSingly node) {
    if(node == null)
        return null;

    LinkedListNodeSingly new_head = null;

    //base case, where we swap the head (very first node) with the tail (very last node)
    if(node.next == null) {
        new_head = node; //node is tail here
        return new_head; //don't need a return overall, really
    }

    //don't need a return overall, really
    new_head = reverseUsingRecursion(node.next);

    /* This next line is key.  It is better understood with an example. 
     * For list 1 2 3 4, we refer to each node by the data, e.g.: node 4 is the last (tail) node.
     * Going over the call stack:
     *  1. base case reached after 4th call to reverseUsingRecursion: return new_head == node 4 
     *  2. returning from base case, we're at node 3's frame: 
     *      2.1 We want node 4 to point back to node 3.
     *          Since node3.next == 4, node3.next.next = node3 sets node4.next to node3
     *      2.2 Since we want node3 to no longer to point to node4, we do node3.next = null.
     *          This breaks the previous direction of the singly list list between these two nodes.
     *          Q: Would we swap here if we were reversing a doubly linked list?
     *      2.3 We return the new head, node 4, all the way up to the first frame (to the first call to reverseUsingRecursion)
     *      2.4 At each return, we restore the frame for the previous node (e.g., point node3 to node2, after pointing node4 to node3, etc...)
     */    
    node.next.next = node;
    node.next = null;

    return new_head;
}