One of the most common test and interview questions is a spinoff of: write a function that reverses a linked list. The interviewer will be looking to see not only if you can make a working function, but if you can make a very efficient one. In this article, we'll discuss the problem statement in more detail, brainstorm until we find an efficient way to solve the problem, discuss that solution, and write the function in multiple programming languages. We'll solve the problem for a few different types of linked lists.
Linked Lists
A linked list is a type of data structure where we represent a list of items using nodes which hold references to each other. The nodes will hold different types of references and properties depending upon what kind of linked list we are using. For a more detailed overview of linked lists, please visit our introduction to linked lists.
Analysis: How to Reverse a Linked List
We must implement a function which reverses a linked list. This means that the end result should be a list which has all of the same elements, but the 1st element now appears last, 2nd now appears 2nd to last, etc. We must find a way to "flip" the node references so each node points to the previous node instead of the next node. In a brainstorming session, the first idea which comes to mind might be to use an array to help with the reversal process. There are a few possible approaches with arrays, most of which will look something like this:
- Initialize an empty array of nodes. If we don't know the length of the list, this will need to be an ArrayList or similar type of dynamic size array class.
- Traverse the linked list with a loop.
- For each item in the list, push that item to the array.
- After all items are added, reverse the array.
- Iterate over the array, and set the next reference of the previous node in the array to that node.
In this type of approach, we will need to allocate space for an array of potentially unknown size, duplicate the number of node references (as each node.next will also appear in the array), then perform another full iteration over that array to reassign the node references. Though it will succeed in reversing the linked list, this approach will waste both space and time by storing redundant references and iterating through the entire list more than once.
To find the most optimial implementation, we will need to consider an algorithm which does not use an array, and which only iterates over the list once. Let's consider the consequences of these limitations:
- If we cannot use an array: we will only be able to store a small, constant number of node references at once.
- If we cannot iterate more than once: we will need to fully process a node and update its next ref appropriate as we receive it, as we will not have access to it after moving past it.
In the point above, we noted what while we cannot keep all nodes in an array, we can keep a small, constant number of nodes. In the approach we'll take below, we will create node references called prevNode, currNode, and nextNode. As we iterate through the list, we'll have 3 additional node references so we can access the node right before and right after the node we're currently visiting. For each iteration, we will:
- Get the next node reference from currNode and assign it to nextNode.
- Update the nextNode reference of currNode and set it to prevNode.
- Set prevNode to currNode.
- Set currNode to nextNode.
In the sections below, we'll cover the code implementation for different types of linked lists and discuss how they differ from eachother.
Reverse a Singly Linked List
The code shown below is a direct implementation of the algorithm given above. The node data type is represented by a class whose implementation is not included here. That class has the following methods:
- getNext(): return the node this node is linked to, or null if none.
- setNext(node): set the next reference and link this node to the provided node, or null.
Reverse a Doubly Linked List
This implementation is similar to the previous one, but we must now account for the fact that nodes can now reference previous nodes as well as next nodes. While iterating, we must update both references at once. The node class has the following methods:
- getNext(): return the node this node is linked to, or null if none.
- setNext(node): set the next reference and link this node to the provided node, or null.
- getPrev(): return the node which linkes to this node, or null if none.
- setPrev(node): set the prev reference and link the nodes, or null.
Reverse a Circular Linked List
This algorithm is very similar to the first one, but since the link is circular, we cannot exit when the next node reference is null, because that situation will never occur. Instead, we must exit when the next reference is equal to the head node itself. Therefore, we will use a do while loop instead of a while loop. We must also complete the cycle with one additional reference update at the end.
- getNext(): return the node this node is linked to, or null if none.
- setNext(node): set the next reference and link this node to the provided node, or null.