Reviewing for interview questions, I ran across this. Most solutions you’ll find are in C, and that can be easily adapted … however, the C-ness sometimes gets in the way of spotting the subtleties. Here is the function in Java,
static void Node reverse(Node head) {
Node current = head;
Node newHead = null;
while (current != null) {
Node tmp = current;
current = current.next;
tmp.next = newHead;
newHead = tmp;
}
return newHead;
}
So how does it work? In a nutshell, we always have 2 lists: 1) the remaining portion of the original list pointed to by current, and 2) the new list pointed to by newHead. Each iteration strips the head element from the original list, and adds it to the head of the new list.
- line 5 saves the current loop pointer, this will be our new head at the end of each loop.
- line 6 advances the current loop pointer one past the head, but remember we saved the old current pointer in tmp at line 5.
- line 7 assigns the next pointer of our new head (tmp) to the previous head pointer. The first time through the loop, this is null, and we’ll have a new list containing one item.
- line 8 permanently tracks our new head by moving it out of the temporary loop var.
I can’t imagine it gets better than this. No new allocations, and O(n).
Zero Credibility 
Nice example and analysis. Do you have more to share with us?
[]s
can u make ex for how to merge two list in new list and return
i get an error when i try this code on line 6 and 7 with the next
Why we just can’t change pointers in head and end elements. It is easier way.
you still need to fix up the next pointer in every element. i.e., you find the tail, and then assign your head pointer to it. now if you go head.next, you get null pointer exception because tail.next == null.
Here is my solution (recursive):
public void reverseList(){
reverseNode(null,head);
}
private void reverseNode(Node parent, Node node){
if(node.child != null){
reverseNode(node,node.child);
} else {
this.head = node;
}
node.child = parent;
}
public void reverse() {
Node current = first;
Node newRoot;
newRoot = null;
while (current != null) {
Node tempNode = current.next;
current.next = newRoot;
newRoot = current;
current = tempNode;
}
first = newRoot;
}
You’ve lost the first element? Did you try the code?
yes i’ve run the code. if you think there’s a bug, be more specific.
Sorry, my bad. Your code works.
Nice code Jeffrey, you saved my 2 hours by providing this code. Small fix needed towards the return type:
“static Node” instead of “static void Node”