Understanding the reversal pattern

Many doubly 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 the list using loops in multiple passes, it is not the best way to do it, as the code is complicated and error-prone. Just like the singly linked list, the most concise and efficient way to reverse a doubly linked list is to use a single-pass in-place reversal algorithm (in-place means we rearrange the existing nodes without allocating a new list), 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 doubly linked list denoted by head and need to reverse it completely.

We initialize two references newHead and current with null and the head of the list respectively and traverse the list from head to tail using current. In each iteration, we swap the next and prev section of the current node and move it forward by one step (after the swap, the original next is stored in prev, so moving forward means setting current to current.prev). We save the reference of the tail node in newHead when we reach it as it will be the head of the reversed list (we know we have reached the original tail when current.next is null after the swap, since the original tail's prev was null). At the end of all iterations, the entire list will be reversed and newHead will be the head of the reversed list.