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.