Reverse a linked list

A Linked list is versatile data structure because of its dynamic nature.  Linked list is versatile and dynamic because insertion or deletion can be done at any given location. Algorithm Complexity of insertion and deletion algorithms are of the order of O(1). Reverse a linked list is another important operation. Let’s read how it is done.

How to Reverse a Linked list?

To reverse a linked list, three pointers are required to maintain addresses of the nodes being reconnected.  Reversal is done by using the traversal operation. The first node becomes last node and last node of the linked list becomes first node after reversal. For every node these actions are done-

  • Store current address of current node in pointer PTR. Store address of previous node in pointer PREV. Store address of next node in pointer NEXT
  • Update LINK of PTR node with LINK of PREV node
  • Update PREV with PTR, PTR with NEXT and NEXT with LINK of NEXT
  • When the  PTR is NULL (reaches end of  the linked list), update START=PREV

These steps are described in the following images.

Reverse a Linked List
Reverse
reverse list

Algorithm

Algorithm  ReverseLL(START)
This algorithm traverses and reverses the  nodes by updating their LINK part.
1. [Initialize Pointers]
   PREV=NULL
   PTR=START
   NEXT=START->LINK
2. Repeat step 3 while PTR!= NULL
3. [Update Pointers]
   PTR->LINK=PREV
   PREV=PTR
   PTR=NEXT
   NEXT=PTR->LINK
4. [Reset Start pointer of Linked List]
   START=PREV

This is the process of reversing a linear linked list by updating the pointers. You can see that this is done without moving the elements physically. It is traversal along with updating the links. The number of nodes in the linked list define the complexity of the algorithm.

Complexity of Algorithm to Reverse a Linked List

Step 2 of the algorithm described determines the major chunk of steps involved in this process. If the number of elements of a linear linked list is N then N nodes will be updated with new values for LINK parts.

So, it can be said that complexity of reversal of a linked list is O(N) and is linear. Time to reverse a linear linked list grows with number of nodes.

Be First to Comment

Leave a Reply

Your email address will not be published.