Reverse linked list from header node?

Question

Everywhere on net I see the program which start revering from tail like

here node is the header node

reverseNode(int node){

    if(node==null){
        return;
    }

    reverseNode(node.next);

    Node temp = node.next;
    node.next = node.prev;
    node.prev=temp;

    if(node.prev==null){
        headNode = node;
    }
}

But I can think of approach where i can reverse from header node also like

here node is the header node

reverseNode(int node){

    if(node==null){
        return;
    }

    Node temp = node.next;
    node.next = node.prev;
    node.prev=temp;


    reverseNode(node.prev);

   if(node.prev==null){
       headNode = node;
   }
}

But I do not see approach mentioned anywhere. Is there any bug/issue in this approach or its not optimized ?

score 0 · Answer 1 · edited May 23 '17 at 12:16

0

The first version is an example of head recursion. The second is an example of tail recursion. Excellent explanation here: The difference between head & tail recursion.

edited May 23 '17 at 12:16

Community

1
1

answered Jul 09 '16 at 15:23

Soggiorno

760
9
17

So my second approach is good in context of reversing the linked list – emilly Jul 09 '16 at 15:28
Yes, your approach works and will, generally speaking, be more efficient in terms of space than the head recursive one as it functions more like a loop (less state is popped on the call stack because the bulk of the work is done before the recursive step). – Soggiorno Jul 09 '16 at 15:30
Related: http://stackoverflow.com/questions/33923/what-is-tail-recursion – Soggiorno Jul 09 '16 at 15:33
1

@Soggiorno Except that Java doesn't implement tail-recursion as a loop, so head- vs. tail-recursion makes no difference. See [Why doesn't Java have optimization for tail-recursion at all?](http://programmers.stackexchange.com/q/272061/202153) – Andreas Jul 09 '16 at 15:35
@Andreas True, in Java it doesn't make a difference as Java has no support for tail recursion. In other languages, that support this feature, it could make a difference, however. – Soggiorno Jul 09 '16 at 15:39
Agreed, and since the linked answer says that Java will eventually get it, if you start writing for it now, it'll improve once Java gets it, and you'll also be prepared to jump to other languages that already has it *(talking about learning experience, not code conversion, though that too)*. – Andreas Jul 09 '16 at 15:48

Reverse linked list from header node?

1 Answers1