Reversing a Singly Linked List

Introduction

Many people have asked me to explain the dynamics of how the reversing of a singly linked list works, when we do not have the liberty of creating a new linked list, may be due to limitation of memory.

The Idea behind Reversing a Singly Linked List

The idea is to iterate through the complete linked list and maintain three pointers as listed below:

  • Pointer to the head of un reversed list headOfUnReversedLL.
  • Pointer to the head of reversed list headOfReversedLL.
  • Pointer to the node to be reversed nodeToReverse.

In each iteration we follow the below four steps:

  1. The headOfReversedLL pointer must point to the nodeToReverse. Initially the node to reverse is null, so the head of reversed linked list will point to null.
  2. The nodeToReverse pointer should point to the head of the un reversed list as we are trying to reverse that particular node.
  3. The headOfUnReversedLL pointer should move one step forward in the un reversed linked list.
  4. The next pointer of nodeToReverse node should point to the head of the reversed linked list.We repeat the above four steps till the headOfUnReversedLL points to null.

Isn’t it simple?

Here is a pictorial representation of the iteration. Each row represents the state of the linked list after one iteration
Reversing a Singly Linked List
So, if we observe closely the first step is actually the finalizing step of the iteration. That is the step which correctly positions the headOfReversedLL to the node which was reversed in the last iteration.

But when the loop exits out, we never get a chance to do that one last time. So at the end, let us re-position the headOfReversedLL to the correct node nodeToReverse

Source Code – Reversing a Singly Linked List

For the complete source code please visit the github repository

Analysis – Reversing a Singly Linked List

Running Time

We just run through the linked list once and hence the time complexity is O(N) where N is the size of the linked list.

Space Complexity

We just use three more pointers and that is not dependent on the size of the linked list, its O(1). Hence, we can say that the space used is constant.

Don’t forget to subscribe to TechieMe to get updates on latest posts.