So, I was learning DSA in java and came to reversing a linked list. I understood the iterative method, but while learning the recursive method there was a point in time where the recursion does two things :

1. reverse the links
2. traverse to the bottom of the list and determine the new head

Q1. Which comes first?(step by step please) The stack is traversed to the bottom and while on its way up reverses the links and returns the new head OR The link is reversed on its way bottom and when reached, returns the new head to the top.

Q2. How does the new node be returned to the recursion above it(step by step please)?

If I'm understanding it wrong can someone please explain it to me how the recursion works in depth? not just by stating leave it to recursive leap of faith. I want to understand it in full depth and its steps.

CodePudding user response：

• Q1: Traverse the list to the end and preserve backlink on stack, return new head to the top. (The other way is also possible see below behind the output.)

• Q2: The idea is always to return the new head but not to return it immediately. After returning from a recursive call first switch the direction (utilizing information maintained on the stack for the current node) and then return (pass through) the new head. The clue is to put two references on the stack so that the link direction can be reverted for each list element.

ReverseList.java

class ListElement {
    String name;
    ListElement next;
    ListElement(String name, ListElement next) {
        this.name = name;
        this.next = next;
    }
}

 public class ReverseList {
    static ListElement reverseList(ListElement previous, ListElement node) {
        if (node == null) { // reached end directly behind last node
            return previous; // new list head
        } else {
            ListElement newHead = reverseList(node, node.next);
            node.next = previous; // turn link direction
            return newHead; // pass through new list head
        }
    }

    static void printList(ListElement list) {
        while (list != null) {
            System.out.print(list.name   " -> ");
            list = list.next;
        }    
        System.out.println("null");
    }

    public static void main(String args[]) {
        ListElement c = new ListElement("c", null);
        ListElement b = new ListElement("b", c);
        ListElement a = new ListElement("a", b);

        ListElement head = a;
        printList(head);
        head = reverseList(null, head); // new list end and head of list
        printList(head);
    }
}

Let's see what we got:

$ javac ReverseList.java
$ java ReverseList      
a -> b -> c -> null
c -> b -> a -> null
$  

It is also possible to turn the link direction while stepping down:

        else {
            ListElement tmp = node.next;
            node.next = previous; // turn link direction
            return reverseList(node, tmp); // pass through new list head
        }

Nevertheless, I prefer to reach the end (bottom) first before modifying the list. This prevents broken linkage in case of a stack overflow.