Reversing a Singly Linked List

This article is part of article series - "Datastructures"

Previous Article: Deleting a Node from a Singly Linked List.
Next Article: Detecting a Loop in Singly Linked List - Tortoise and Hare.

Let us see how to reverse a Singly Linked List.

Figure-1: Singly Linked List

Pseudocode:

cur_ptr = HEAD->NEXT
prev_ptr = NULL

forever:

   if cur_ptr == NULL
   break

   tmp_ptr  = prev_ptr
   prev_ptr = cur_ptr
   cur_ptr  = cur_ptr->NEXT
   
   prev_ptr->NEXT = tmp_ptr

HEAD->NEXT = prev_ptr

Complexity:
Time Complexity: O(n)
Space Complexity: O(3)

If we try on the example in Figure-1 we get the output as shown below

Figure-2: After reversing the Singly Linked List

Previous Article: Deleting a Node from a Singly Linked List.
Next Article: Detecting a Loop in Singly Linked List - Tortoise and Hare.