Reversing a Linked List in Java, Recursively

Reversing a linked list in Java, recursively

There's code in one reply that spells it out, but you might find it easier to start from the bottom up, by asking and answering tiny questions (this is the approach in The Little Lisper):

What is the reverse of null (the empty list)? null.
What is the reverse of a one element list? the element.
What is the reverse of an n element list? the reverse of the rest of the list followed by the first element.

public ListNode Reverse(ListNode list)
{
    if (list == null) return null; // first question

    if (list.next == null) return list; // second question

    // third question - in Lisp this is easy, but we don't have cons
    // so we grab the second element (which will be the last after we reverse it)

    ListNode secondElem = list.next;

    // bug fix - need to unlink list from the rest or you will get a cycle
    list.next = null;

    // then we reverse everything from the second element on
    ListNode reverseRest = Reverse(secondElem);

    // then we join the two lists
    secondElem.next = list;

    return reverseRest;
}

How can this linked list reversal with recursion work?

To see that this works correctly, start with a list having just one node. It is clear that in that case the node is returned as-is by the following if statement:

if (head.next == null) {
    return head;
}

And that is indeed what you would expect: the reversal of a list with one node should not change anything to that list; the head should reference the same single node.

Induction

We could go on now and analyse the algorithm for 2 nodes, 3 nodes, then 4, then 5, etc. But we can instead use a proof of induction here:

Let's say we have a list of any size greater than 1, like this:

 head
  ↓              
┌───────────┐    ┌───────────┐                        ┌───────────┐
│ value: 85 │    │ value: 15 │                        │ value: 20 │
│ next: ———————→ │ next: ———————→ ...more nodes...——→ │ next:null │
└───────────┘    └───────────┘                        └───────────┘

We will then execute:

Node newHeadNode = reverse(head.next);

head->next is a reference to the second node, the one with value 15. This reference is passed on to the recursive call of reverse.

Now each execution of reverse has its own execution context, and in that deeper context we get a new instance of a head variable. It is initialised with the value that was passed as argument. So in this case that head refers to the node with value 15.

To this recursive execution context of reverse this is the first node of a list (as it doesn't know about the node with 85), and its own head variable references it:

                  head
                   ↓              
                 ┌───────────┐                        ┌───────────┐
                 │ value: 15 │                        │ value: 20 │
                 │ next: ———————→ ...more nodes...——→ │ next:null │
                 └───────────┘                        └───────────┘

We now will assume that this call will reverse that shorter list correctly and will return the old tail node, which has become the new head (with value 20):

                  head                                (returned)
                   ↓                                    ↓        
                 ┌───────────┐                        ┌───────────┐
                 │ value: 15 │                        │ value: 20 │
                 │ next:null │ ←——...more nodes... ←——————— :next │
                 └───────────┘                        └───────────┘

Executing return, the deeper execution context disappears, and the returned reference is assigned to newHeadNode in the outer execution context, where head still refers to the node with value 85:

 head                                                  newHeadNode
  ↓                                                     ↓
┌───────────┐    ┌───────────┐                        ┌───────────┐
│ value: 85 │    │ value: 15 │                        │ value: 20 │
│ next: ———————→ │ next:null │ ←——...more nodes... ←——————— :next │
└───────────┘    └───────────┘                        └───────────┘

Note how we assume that:

all the links in that shorter list now effectively point "the other way";
the node that follows head has become a tail node with its next property set to null;
the new head is the previous tail node and a reference to it is returned by the recursive function call.

Then this is executed:

head.next.next = head;

Which is reflected here:

 head                                                  newHeadNode
  ↓                                                     ↓
┌───────────┐    ┌───────────┐                        ┌───────────┐
│ value: 85 │    │ value: 15 │                        │ value: 20 │
│ next: ———————→ │           │                        │           │
│           │ ←——————— :next │ ←——...more nodes... ←——————— :next │
└───────────┘    └───────────┘                        └───────────┘

And:

head.next = null;

This makes sense, because if the list has been reversed, then the head is now the tail, and there should be no other node following the tail node:

 head                                                  newHeadNode
  ↓                                                     ↓
┌───────────┐    ┌───────────┐                        ┌───────────┐
│ value: 85 │    │ value: 15 │                        │ value: 20 │
│ next: null│ ←——————— :next │ ←——...more nodes... ←——————— :next │
└───────────┘    └───────────┘                        └───────────┘

Finally:

return newHeadNode;

So... we see that if our assumption is right, then we have correctly reversed the list.

As we verified it works for a list with 1 node, and we now also found that if it works for a list of size it also works for a list of size +1, we have proof that it works for any list.

How `head` "moves"

You can imagine how the variable head will "walk" to the next node at each deeper recursive call, until it reaches the last node in the list. Then the base case kicks in and no more recursion happens. As the execution backtracks out of recursion, head seems to move back in the opposite direction back to where it started.

Although it can help to see it that way, this is not entirely correct: each execution context of reverse has its own version of head that actually never moves. It is a constant reference. However, as each recursive call gets head->next as argument, the new head variable that exists in the deeper execution context, is initialised with that next node. And so each separate execution context of reverse has a head variable that references a different node. And whenever the execution of one call of reverse ends, execution will fall back into a previous execution context where we deal again with a variable head that didn't move and still references the same node as was the case before the recursive call.

Reverse a linked list recursively in Java

This is a question designed to test whether you understand the implicit stack.
Each time you make a recursive call, you add a stack frame, so consider the stack as if you were performing the routine iteratively.

To reverse the list:

Stack all elements in order
Make a new list by popping each element.

Now convert this to a recursive call

//in [1,2,3,null]
Node reverse(Node n){

    //base case
    if(n == null)
    {
        return null;
    }

    // returns [null,3,2,1]
    Node next = reverse(n.getNext());
    next.setNext(n);// set the next nodes next to its previous(n on unwinding)
    return n;
}

Note that the reverse method here doesn't return the new head, to get the head of the reversed list do the following, maybe making a the above a helper instead.

Node oldHead = n;
Node newHead = tail(n);
oldHead.reverse();

which comes first while reversing a linked list recursively?

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.

Reverse a singly linked list recursively by dividing linked list in half in each recurrence

Because you're working with a linked list, the approach you suggest is unlikely to be efficient. Ascertaining where the midpoint lies is a linear time operation, and even if the size of the list was known, you would still have to iterate up to the midpoint. Because you have a linear term at each node of the recurrence tree, the overall performance will be O(n lg n), slower than the O(n) bound for the code which you have provided.

That being said, you could still reverse the list by the following strategy:

 Step 1: Split the list L into A (the first half) and B (the second half).
 Step 2: Recurse on each of A and B. This recursion should bottom out 
         when given a list of length 1.
 Step 3: Attach the new head of the reversed A to the new tail of the reversed B.

You can see that to begin with, our list is AB. We then recurse to get A' and B', each the reversed version of the half lists. We then output our new reversed list B'A'. The first element of the original A is now the last element of the list overall, and the last element of the original B is now the first overall.

Reversing singly linked list, recursively

When writing recursion, it's usually best to think about the end case(s), then write the recursive case last. The other thing about recursion is its extremely useful to return the result.

Yes, your solution is technically recursive, but I don't think the code works. At the line current.next = head, head is not defined, unless this code is in some class that you've not shown. Worse yet, it may infinite loop, because at the beginning of the function, tail = p and at the end your recursion is called with tail, thus an infinite loop. At best this will reverse a list of length 3, but not a list of any length.

In Java, the recursive function often needs a "helper" function to get it started. First, assume the following node class:

public class Node{
    public object data;
    public Node next;
}

And given the problem statement, I'm assuming we're not allowed to play with the data pointers, just the next pointers. This code would be some other class than Node.

public Node recursiveReverse(Node p)
{
    return helperReverse(p, null);
} 

private Node helperReverse(Node p, Node previous)
{
    if (p == null)
    {
        return p;
    }
    else if (p.next == null)
    {
        p.next == previous;
        return p;
    }
    else
    {
        Node next = p.next;
        p.next = previous;
        return helperReverse(next, p);
    }
}

It gets even better if it's incorporated in the Node class.

public class Node{
    public object data;
    public Node next;

    public Node reverse() {
        return reverse1(null);
    } 

    private Node reverse1(Node previous) {
        if (next == null) {
            next == previous;
            return this;
        }
        else {
            Node other = next;
            next = previous;
            return reverse1(other, this);
        } 
    }

}

Enjoy!

Reversing a Linked List in Java, Recursively