Reverse a Linked List, Java

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).

Advertisements

11 Responses to Reverse a Linked List, Java

  1. Pedro says:

    Nice example and analysis. Do you have more to share with us?

    []s

  2. nice says:

    can u make ex for how to merge two list in new list and return

  3. new says:

    i get an error when i try this code on line 6 and 7 with the next

  4. Max says:

    Why we just can’t change pointers in head and end elements. It is easier way.

    • Jeffrey Blattman says:

      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.

  5. Ivan says:

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

  6. elbek says:

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

  7. vibneiro says:

    You’ve lost the first element? Did you try the code?

  8. PK Jajara says:

    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”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: