I would like to know if this is a valid recursive solution and if any improvements can be made. I've tested this solution with a few inputs and it seems to work.
public Node reverse(Node head) {
if(head == null) {
return null;
}
if (head.next == null) {
this.head = head;
return head;
}
Node n = head.next;
head.next = null;
reverse(n).next = head;
return head;
}
Thank you.
In terms of algorithm, I think this method does what you want, I believe you wanted a linked list
A->B->C
to be converted to
C->B->A, and return A.
I am just a little confused with the scope of this method, is it a instance method of Node? what "this" is at line 8.
One thing I am not sure is, if you do not keep other pointers to C and B, after the reverse is done, then you are left with the list C->B->A, with a returned pointer to A. It looks like C and B are not pointed by any variables, won't it be garbage collected? and removed? Maybe this problem is solved by the "this" thing.
A good practice of constructing a list should be a method that return the head of a list. But your method returns the tail. I suggest make this an instance method of Node, then you make the reverse() method to be called with head, and return the new head
something like this, but I have not tested the code