Reversing a Linked List

22 Oct 2009. comments

A very common CS problem is to reverse a linked list without using recursion. If you’ve never done it before it can be challenging, especially if you don’t think visually. I found it useful to draw it out on a whiteboard so I could see the algorithm step by step.

The basic idea here is to maintain 3 pointers as you work your way along the list chain.

  1. The previous node so that you don’t lose what you’re going to point the current node’s next pointer at.
  2. The current node.
  3. The next node so that when you point the current node’s next pointer at the previous node you don’t lose the reference to move on to next.

At each node along the chain you point the current node’s ‘next’ pointer to the previous node and ‘inchworm’ your way forward until you’ve hit all nodes. At the end repoint the ‘head’ to be where you’re at.

Here is what that might look like in Java. I added comments to help illustrate each step since it can sometimes be hard to map what you see in code to how the algorithm is described abstractly.

class LinkedList {

  public void reverse() {

    if(this.head == null || this.head.next == null) {
      // nothing to do because its an empty list, or a list with 1 element
      return;
    }

    // here are those pointers I talked about above
    Node previous = null;
    Node current = this.head;
    Node next = this.head.next;

    // inchworm through the list until the end
    while(next != null) {

      // make this one point backwards instead of forwards
      current.next = previous;
      
      // move your pointers to the next set of links
      previous = current;
      current = next;
      next = current.next;

    }

    current.next = previous;

    // the new head is the former tail
    this.head = current;

  }

}

Thats pretty much it. I don’t think it makes for a particularly good interview question since you aren’t really going to be doing anything like this as part of any job (you will use the standard library in your language) but I do think its important to understand it and contrast it with other data structures (like arrays) to understand the different performance reasons why you might want to use one over the other.

comments

Tagged: java data structures algorithms Katas interview

2017 Ben Lakey

The words here do not reflect those of my employer.