## 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:

- 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. - The
**nodeToReverse**pointer should point to the head of the un reversed list as we are trying to reverse that particular node. - The
**headOfUnReversedLL**pointer should move one step forward in the un reversed linked list. - 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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 |
private Node reverse(Node h0) { Node headOfUnReversedLL = h0; Node headOfReversedLL = null; Node nodeToReverse = null; while (headOfUnReversedLL != null) { headOfReversedLL = nodeToReverse; nodeToReverse = headOfUnReversedLL; headOfUnReversedLL = headOfUnReversedLL.next; nodeToReverse.next = headOfReversedLL; } headOfReversedLL = nodeToReverse; return headOfReversedLL; } |

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.