How about doing it in place?
I think this works. Didn't test the full iteration, wrote in one go.
Get the first 3 nodes (if the list is less than 3, then just change the pointers). Iterate through list reversing the pointers of the first 2 tracked nodes, keep 3rd node as reference for the next iteration. I return the new root node:
public Node reverseLinkedList(Node n) {
if (n == null) return null;
if (n.next == null) {
return n;
}
Node nN = n.next;
if (nN.next == null) {
n.next = null;
nN.next = n;
return nN;
}
Node nNN = nN.next;
n.next = null;
while (nNN.next != null) {
nN.next = n;
n = nN;
nN = nNN;
nNN = nNN.next;
}
nNN.next = nN;
return nNN;
}