Reverse a Linked List

In this article, we will solve a commonly asked problem on linked lists which is reversing a linked list. Given a singly linked list, our goal is to reverse the order of its nodes i.e. reverse the linked list.

Example:

Original Linked List:

1 -> 2 -> 3 -> 4 -> 5 -> NULL

Reversed Linked List:

5 -> 4 -> 3 -> 2 -> 1 -> NULL

Solution:

Reversing a linked list can be done iteratively or recursively. In this article, we will focus on the iterative approach, which is commonly used due to its simplicity and efficiency.

Explanation:

·       Initialization: The prev is initialized to NULL. It will eventually become the new head of the reversed list. The curr is initialized to head, which points to the current node.

·       Iteration: We will loop through the list until curr becomes NULL. Here inside the loop, we store the next node of curr in nextTemp to keep track of the remaining part of the list.

·       After that, we reverse the current node's pointer by setting curr->next to prev.

·       We then move the prev pointer one step forward to curr and move the curr pointer one step forward to nextTemp.

·       Once the loop completes, prev will be pointing to the new head of the reversed list, and hence we return prev.

Time Complexity: O(n)

Space Complexity: O(1)