Coding interview Essentials

21. Reverse a singly linked list

Reverse a singly linked list

Introduction

In this chapter we are going to have a look at a problem based on reversing a singly linked list. Despite the fact that this is one of the fundamental structures in computer science and is also an extremely popular interview question, it often trips up prospective candidates and is usually a cause for immediate rejection. As such, it is worth spending a bit of time on it to ensure a solid grasp of the optimal solutions.

The problem has a simple definition as all it asks us to do is reverse a given list. We will discuss how we can approach this problem both a recursive and an iterative manner. We will also examine a slightly harder variation that is often asked as a follow-up although we leave the solution to that one for the reader.

Problem statement

Create a function that, given a singly linked list \(L\), reverses it and return the pointer to the new head of \(L\). \(L\) is given as a pointer to the first node of the list. The definition of the node is given in Listing [list:list_reverse:node_definition].


Given the \(L = 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5\), the function modifies it into \(L = 5 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 1\) and returns a pointer to the node \(5\), the new head of the list.

Listing 1: Singly linked-list node definition.

template <typename T>
struct Node
{
  T val;
  Node *next;
  Node() = default;
  Node(T x) : val(x), next(nullptr)
  {
  }
};

Clarification Questions

Can the input list be empty?

Yes.

Can I assume \(L\) is not corrupted by e.g. containing cycles?

Yes, the input list is a singly linked list with no cycles.

Discussion

Solving this problem using linear additional space is trivial as we can iterate over the list and for each push the address of each of its nodes in a stack. We can then pop them one at a time while making sure they are connected in the same order they are popped out. Listing [list:list_reverse:stack] shows a possible implementation of this idea. The time and space complexity of this approach is \(O(n)\).

Listing 2: Linear time and space complexity solution using a stack to reverse the nodes in the list.

template <typename T>
Node<T>* list_reverse_linear_space(Node<T>* L)
{
  if (!L)
    return nullptr;

  std::stack<Node<T>*> nodes;
  Node<T>* it = L;
  while (it)
  {
    nodes.push(it);
    it = it->next;
  }

  Node<T>* new_head = nodes.top();
  nodes.pop();

  it = new_head;
  while (!nodes.empty())
  {
    const auto it_next = nodes.top();
    nodes.pop();
    it->next = it_next;
    it       = it_next;
  }
  it->next = nullptr;
  return new_head;
}

We can, however, avoid using additional space in the form of a and rely on the implicit stack we get when we perform recursive calls. In order to take advantage of it, however, it is convenient to shift our view of the problem as follows:

Imagine we have a list such that it is already reversed after its \(k^{th}\) node. How can we then reverse the rest of it? Let’s have a look at Figure 25.1 depicting this scenario where \(k=4\). As we can see the list is already reversed from node \(5\) onwards and all we have to do is to have it pointing to node \(4\) and make \(4\) point to nothing. More generically what we want to achieve is to make the node \(k+1\) (\(L_{k+1}\)) point to the node \(k\) (\(L_{k+1}\)). We can achieve this by doing: \(L_{k} \rightarrow next \rightarrow next= L_{k}(L_{k+1}\)). With regard to Figure 25.1 \(L_{k} \rightarrow next\) is \(5\) and \(L_{k} \rightarrow next\) is pointing to nothing. After these operations what we are left with is the list shown in Figure 25.2. If we do that for each of the nodes eventually we are left with a reversed list.

Figure 1: Nodes arrangements in the middle of the recursive process for node 5
Figure 2: Nodes arrangements after performing the recursive call for node 5.

But what about the new head of the list? What should each recursive call return? This is actually fairly straightforward. Whenever we reach the end of the list[^23] we return the current node - which is effectively the new head of the reversed list - and we keep propagating that value for all the recursive calls.

To summarise, for each recursive call we first reverse the rest of the list and we get back the head of the reversed list. We can now take care of reversing the link from the current node to the next and return the head we got back from the recursive call. Listing [list:list_reverse:recursive] shows a possible implementation of this idea. Note that despite this solution not explicitly using any additional space, it still requires spaces for the activation frames of all the recursive calls. As such, its complexity remains equivalent to the one in Listing [list:list_reverse:stack].

Listing 3: Recursive linear time and space complexity solution to reverse the nodes in the list.

template <typename T>
Node<T>* list_reverse_recursive(Node<T>* L)
{
  if (!L || !(L->next))
    return L;

  auto reverse_next_head = list_reverse_recursive(L->next);
  L->next->next          = L;
  L->next                = nullptr;
  return reverse_next_head;
}

Constant space

It is impossible to solve this problem faster than linear time as each node must be accessed at least once; but we can bring the space complexity down to constant. We do this by reversing the list, two nodes at a time, from the head to the tail. Assuming \(L\) has at least two nodes (if not we are in a trivial case in which the list is already reversed and \(L\) is also the head of the reversed list) then we can always maintain two pointers to the current element and its next . We know that points to but what we really want to achieve is pointing to \(curr\). We can take care of that and proceed with moving curr and forward and repeat the process. Eventually we will have reversed all nodes in the list. This process ends whenever we reach the last node of the list; which also happen to be the new head of the list.

An implementation of such idea is shown in Listing [list:list_reverse:constant_space]. Note that while making point to we must also remember the element points to, otherwise it would be impossible to move and forward. Figure [fig:list_reverse:list_reverse_iterative_execution] shows the execution of the algorithm in Listing [list:list_reverse:constant_space] on a list of \(7\) elements.

Listing 4: Iterative constant space solution to the problem of reversing a list.

template <typename T>
Node<T>* list_reverse_constant_space_iterative(Node<T>* L)
{
  if (!L || !(L->next))
    return L;

  auto curr      = L;
  auto curr_next = curr->next;
  curr->next     = nullptr;  // the first node is the new tail
  while (curr && curr_next)
  {
    auto temp       = curr_next->next;  // needed to move forward curr_next
    curr_next->next = curr;
    curr            = curr_next;
    curr_next       = temp;
  }
  return curr;
}
Figure 3: Step 1
Figure 4: Step 2
Figure 5: Step 3
Figure 6: Step 4
Figure 7: Step 5
Figure 8: Step 6
Figure 9: Step 7. is the new head of the reversed list.

Conclusion

We have discussed three possible approaches to the problem of reversing a singly-linked list. We saw that it is almost trivial when using an iterative approach together with a stack to store the addressed of the list’s nodes. This approach is based on the fact that the ordering of \(n\) elements popped from a stack is the reverse of the ordering the elements have been pushed on to.

We then examined an alternative solution that, whilst based based on the same stack idea, does not use an explicit stack to store the nodes but rather stores the same information in the call stack of the recursive function.

Finally, we discussed a solution where only a constant space is required. This approach works iteratively from the head to the tail of the list by reversing two nodes at a time.

Common variation - Reverse a sublist

Problem statement

Create a function that, given a singly linked list \(L\) and two integers \(n \geq m \geq 0\), reverses only its nodes from the \(m^{th}\) to the \(n^{th}\) and return the pointer to the new head of \(L\). As in the other version of this problem discussed above the definition of a node is the same and the list \(L\) is given as a pointer to the first node of the list itself.


Given the \(L = 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5\), \(m = 3\), \(n = 5\) the function modifies it into \(L = 1 \rightarrow 2 \rightarrow 5 \rightarrow 4 \rightarrow 3\) and returns a pointer to the node \(1\).


Given the \(L = 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5\), \(m = 1\), \(n = 2\) the function modifies it into \(L = 1 \rightarrow 2 \rightarrow 5 \rightarrow 4 \rightarrow 3\) and returns a pointer to the node \(1\).