Understanding the reversal pattern

Many linked list problems require us to reverse the entire list or a part of it. For some problems, we may have to perform a reversal many times along with other more complex operations. While we can reverse a linked list using loops in multiple passes, it is not the best way to do it, as the code is complicated and error-prone. The most concise and efficient way to reverse a linked list is to use a single-pass in-place reversal algorithm, which is a very simple four-line algorithm.

In this course, we will learn more about the linked list reversal algorithm and how to identify a problem as a reversal pattern problem.

Reversing the entire list

Reversing the entire linked list is a special case of the generic reversal algorithm to reverse a segment between start and end. We first look at this special case as it has a much simpler implementation and is used in most linked list problems that require a reversal. Consider we are given a linked list denoted by head and need to reverse it completely.

We initialize two references previous and current with nullptr and the head of the list respectively and traverse the list from the head node using current. We save the reference of the node after current in a reference variable next, set the next section of each node to previous and update previous and current for the next iteration.

At the end of all iterations, the entire list will be revered, and the previous will hold the head of the reversed list.

Algorithm

The algorithm below summarizes the reversal of the entire linked list in-place.

Algorithm

• Step 1: Create two references, `previous` and `current`, and initialize them with `nullptr`, and `head` respectively.
• Step 2: Loop while `current` is not equal to `nullptr`, do the following:
  • Step 2.1: Initialize a reference `next` to store the reference of the node after the `current` node.
  • Step 2.2: Update the next section of the `current` node to hold the node held by `previous`.
  • Step 2.3: Update `previous` to hold the reference of the `current` node.
  • Step 2.4: Update the `current` to hold the node held by `next`
• Step 3: Return `previous` as the head of the reversed list.

Implementation

The code implementation to reverse the entire list is given below.

Complexity Analysis

We traverse the entire list to reverse it in place, and so the runtime complexity is linear O(N) in any case.

Since we do not create any new data structure while reversing the list, the space complexity is constant O(1) in any case.

Best Case -

• Space Complexity - O(1)
• Time Complexity - O(N)

Worst Case

• Space Complexity - O(1)
• Time Complexity - O(N)

Reversing a segment

Reversing a segment between two nodes is the generic case of the reversal algorithm. Consider we are given a singly linked list and references to two nodes, start and end, and we need to reverse the segment (including start and end).

To connect the first node of the segment back to the list after reversal, we need to know the node after end. We create a reference variable rightBound and initialize it with the node after end.

Next, we initialize two references previous and current with the rightBound and start respectively and traverse the list from start to end using current.

In each iteration, we save the reference to the node after current in a reference next to use it later. We then set the next section of current node to previous.  We then set previous to current and current to next for the next iteration. At the end of all iterations, the node held in previous becomes the new head of the reversed segment.

The last step is to connect the reversed head back to the list. As we will see later when solving problems that use the reversal technique, this is generally done by the caller of the reverse algorithm, which has the references to the node before start. 

Algorithm

The algorithm given below summarizes the linked list reversal between start and end.

Algorithm

• Step 1: Create three references, `previous`, `current`, and `rightBound` and initialize them with `end.next`, `start`, and `end.next` respectively.
• Step 2: Loop while `current` is not equal to `rightBound`, do the following:
  • Step 2.1: Initialize a reference `next` to store the reference of the node after the `current` node.
  • Step 2.2: Update the next section of the `current` node to hold the node held by `previous`.
  • Step 2.3: Update `previous` to hold the reference of the `current` node.
  • Step 2.4: Update the `current` to hold the node held by `next`
• Step 3: Return `previous` as the new head of the list and connect the node before `start` to this new head in the caller of this reverse function.

Implementation

Given below is the code implementation to reverse a linked list between start and end.

Complexity Analysis

We only traverse the linked list between the start and end to reverse the segment. In the worst case start and end maybe the beginning and the end of the list, so we will have to traverse the entire list, which takes linear O(N) time. In the best case, however, start and end maybe the same node, and we won't traverse at all, leading to constant O(1) time.

Since we do not create any new data structure while reversing the list, the space complexity is constant O(1) in any case.

Best Case - start and end are the same node.

• Space Complexity - O(1)
• Time Complexity - O(1)

Worst Case - start and end are the head and tail of the list.

• Space Complexity - O(1)
• Time Complexity - O(N)

Applications

Many linked problems may be classified as reversal pattern problems. Some may be solved by directly applying the reversal algorithm, while others may comprise one or more subproblems that can be solved using the reversal algorithm. We further classify the reversal pattern problems as follows.

• Direct application
• Subproblems

Later in the course, we will examine techniques for identifying all categories of the reversal pattern problems.