Reversing a Linked List

linked listA common interview challenge, for software engineers/developers, is to implement an algorithm to reverse a linked list. Although this is not very common in practice, it is a good way to infer your knowledge of linked lists and how to manipulate/view objects in memory.

We will reverse a linked list, both via recursion and iteration, or the iterative approach.

Recursion

recursionTo get a more extensive definition of recursive algorithms, please follow this link. Recursion is used to solve complex problems, by combining the solutions obtained by simple versions of the larger problem. This calls for base cases, to denote when the algorithm has finished processing.

In our example, our base case is met when we reach the end of the node list. Take this implementation, written in Java:

public Node reverse(Node head, Node previous)
{
   if(head == null)
   {
	return previous;
   }

   ListNode temp = head.getNext();
   head.setNext(previous);
   return reverseRecursive(temp, head);
}

We will note that line 25 defines the “reverse” method, where we are returning an object representing the first object in a linked list, presumably the head node. So this assumes we would call this method like so:

headOfList = reverse(headOfList, null);

This would now make the headOfList variable represent the last node in the list, which would point to the second to last, etc. The reference to the previous node would initially be called with a null value. More on that later.

   if(head == null)

Line 27 is the base case. In other words, if the head node is null, we simply return whatever value the previous node is. This lets our algorithm know that we have reached the end of the list we are to reverse.

   ListNode temp = head.getNext();
   head.setNext(previous);
   return reverseRecursive(temp, head);

Lines 32-34 do the work of first creating a temporary Node that points to the Node object that the head Node is pointing/connected to (Line 32). Then the head pointer is set to point to the previous Node object (line 33). Finally, the temporary node is used as the head variable in the recursive call, making the head node the previous Node, in that same call.

Whew! Let’s try to visually see what is happening. Let us say that the link list is represented by this set of numbers, before the first call to the reverse method, where the arrows represent how they connect to one another, i.e. their “Next” node:

[1->2->3->4->5->null]

After the first call, it now looks like this, where previous is 1 and head is 2:

[null<-1 2->3->4->5->null]

In the second call, previous is 2 and head is 3:

[null<-1<-2 3->4->5->null]

Until we get to the base case, previous is 5 and head is null:

[null<-1<-2<-3<-4<-5]

Once you wrap your mind around an algorithm that solves a complex case, by iteratively calling itself via combinations of simple cases, recursive solutions become easier than iterative implementations to read, given the less lines of code needed. However, with large numbers of objects, this solution uses a lot of memory, since a stack frame is created for every recursive call, on the call stack. A call stack is basically a stack of stack frames.

Although not as easy to read, the iterative approach to large numbers of objects is more memory efficient, thus less prone to crashing your system.

Iterative

mountain climbingRather than implementing the solution by stitching together smaller pieces of the problem, the iterative approach will go/loop through the entire problem set, processing each object/value accordingly. This will leave only one stack frame on the call stack, since the respective algorithm is only called once.

To resolve our problem iteratively, we take this approach:

public Node reverse(Node head)
{
    if(head == null)
    {
      return null;
    }

    Node current = head;
    Node previous = null;

    while (current != null) {
      Node next = current.getNext();
      current.setNext(previous);
      previous = current;
      current = next;
    }

    return previous;
}

Line 27 simply guards against the base case, where the head node is null. This also helps prevent any null pointer exceptions further down in the algorithm.

Lines 32 and 33 define the temporary nodes that are going to represent the respective current node to process, as well as the previous node processed.

Lines 35-39 implement a while loop, which processes the entire problem set within one call of the algorithm. Line 36 shows a temporary Node getting the current Node’s next Node. Line 37 will then set the current Node’s next node to the previous Node. Line 38 sets the previous Node to the current Node, and the current Node is finally set to the temporary Node’s value.

The while loop will continue until it gets to the end of the Linked List.

This is a rather long-winded outline of implementing the reversal of a Linked List via two different implementation approaches. However, the ability to implement these two solutions, while weighing the benefits/detriments of each approach, shows that you understand the mechanics of a Linked List, as well as memory management in general.

Rather good insight into an engineer/developer, from such a simple question.

About Rick

I am a father, husband and software engineer, trying to stay active, both in my personal and professional communities. I enjoy programming and building Web applications.
This entry was posted in Algorithms and tagged , , , , . Bookmark the permalink.

4 Responses to Reversing a Linked List

  1. Khuram Ali says:

    You have presented goods examples but if a linked list is created with dynamic memory allocation, we need to take care of our temp nodes.

    • Rick says:

      Thanks for your comment Khuram!

      As you know, “all” objects in Java are dynamically allocated. We’re always just passing references around everywhere. So the beauty of that, and Java, is that we can pass objects around without worrying about where they are stored. For example, this would allocate the object on the heap and a reference to it is stored on the stack:

      Object obj = new Object();

      Once we leave our method, the “temporary” object that points to nodes on the list will be gobbled up by the garbage collector.

      Now, the C++ implementation would be a little different. 🙂

      • Khuram Ali says:

        Yes. i am actaully talking about c or c++ implementation. in Java, we can play arround with memory, thanks to garbage collection.

      • Rick says:

        Ah very good. Yes. The C++ iterative implementation can be approached in a different way, with pointers, where you’d use a pointer to point at either end of the linked list.

        Then each iteration of your algorithm, you would move your pointers to the center of the list, right after you swapped their values.

        The recursive C++ solution is very similar to the Java version, except that you’re pushing pointers, rather than object references.

        I look forward to reading more of the posts on your blog. Thanks again for engaging!

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