# Reverse a linked list recursively

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;
}
curNode.next = prevNode;
}

• What language is this? Please add a language tag. May 9, 2016 at 2:12

### 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.
}

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.

return reversedList;
}


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();
}


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

    ...
}


you should write

    ...
}



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
*
* @return the new head node of the reversed list.
*/
public static Node reverse(final Node head) {
return null;
}

final Node headNodeDummy = new Node(0);
}

/**
* 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.
*/
}

}

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

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

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.