Reverse a linked list recursively

Question

This recursive calls reverseList on each node of the linked list. When returned from the function call, it changes the next link to the previous node.

public static Node reverseList(Node curNode , Node prevNode , Node reverseListHead)
{
    //empty list
    if(curNode == null)
    {
        return null;
    }
    //node with single element
    if(curNode.next == null)
    {
        curNode.next = prevNode;
        reverseListHead = curNode;
        return reverseListHead;
    }
    reverseListHead = reverseList(curNode.next, curNode, reverseListHead);
    curNode.next = prevNode;
    return reverseListHead;
}

Answer 1

Only one argument needed

First of all, your third argument reverseListHead should be a local variable because it is never used before being set.

Next, if you change your algorithm slightly, you don't need the second argument either:

public static Node reverseList(Node head)
{
    // Empty list or list with one element.
    if (head == null || head.next == null) {
        return head;
    }

    Node second = head.next;
    Node reversedList = reverseList(second);

    // The second node is now the tail of the reversed list,
    // so when we append head to it, head becomes the new tail.
    second.next = head;
    head.next   = null;

    return reversedList;
}

Answer 2

1 Algorithm

You can do the same in linear time and space (recursion stack) with only one routine if and passing only two arguments to the actual algorithm routine. (See below.)

2 Coding conventions

In Java, it is advised to write

if (test()) {
    foo();
}

instead of

if (test()) 
{
    foo();
}

Also, you should have one space between if and the opening parenthesis of the condition.

You should have one empty line after the closing brace of an if, for or while and the subsequent statements in the same method. So, instead of

    ...
    return reverseListHead;
}
reverseListHead = reverseList(curNode.next, curNode, reverseListHead);

you should write

    ...
    return reversedListHead;
}

reverseListHead = reverseList(curNode.next, curNode, reverseListHead);

3 API

It would be nice if you had an "entry" method that asks only for one argument: the head of the list to reverse, and that would call a (private) implementation class method.

Summa summarum

All in all, I had the following in mind:

public class Node {

    final int datum;
    Node next;

    Node(final int datum) {
        this.datum = datum;
    }

    /**
     * Reverses the linked list starting from {@code head}. Returns the new
     * head node.
     * 
     * @param head the head of the linked list to reverse.
     * @return the new head node of the reversed list.
     */
    public static Node reverse(final Node head) {
        if (head == null) {
            return null;
        }

        final Node headNodeDummy = new Node(0);
        reverse(head, headNodeDummy);
        return headNodeDummy.next;
    }

    /**
     * Reverses the linked list starting from {@code head}. Returns the new 
     * tail node of the reversed linked list, and sets 
     * {@code headNodeDummy.next} to the first node of the reversed list.
     * 
     * @param head          the beginning of the list to reverse.
     * @param headNodeDummy the node holding the head node of the result list.
     * @return              the last node of the reversed node.
     */
    private static Node reverse(final Node head, final Node headNodeDummy) {
        if (head.next == null) {
            headNodeDummy.next = head;
            return head;
        }

        final Node newTail = reverse(head.next, headNodeDummy);
        newTail.next = head;
        head.next = null;
        return head;
    }

    public static String toString(final Node head) {
        if (head == null) {
            return "[]";
        }

        final StringBuilder sb = new StringBuilder("[").append(head.datum);
        Node current = head.next;

        while (current != null) {
            sb.append(", ").append(current.datum);
            current = current.next;
        }

        return sb.append("]").toString();
    }

    public static void main(final String... args) {
        System.out.println("List lenght = 4:");
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;

        System.out.println(toString(n1));
        n1 = reverse(n1);
        System.out.println(toString(n1));
        n1 = reverse(n1);
        System.out.println(toString(n1));

        System.out.println("List length = 2:");
        n1 = new Node(1);
        n2 = new Node(2);

        n1.next = n2;

        System.out.println(toString(n1));
        n1 = reverse(n1);
        System.out.println(toString(n1));
        n1 = reverse(n1);
        System.out.println(toString(n1));

        System.out.println("List length = 1:");

        n1 = new Node(1);

        System.out.println(toString(n1));
        n1 = reverse(n1);
        System.out.println(toString(n1));
        n1 = reverse(n1);
        System.out.println(toString(n1));

        System.out.println("List length = 0:");

        System.out.println(reverse(null));
    }
}

Hope that helps.