Singly Linked List – Reverse Operation

Reverse Operation in Singly Linked List

Reversing the singly linked list so that the last node becomes the new head and all next pointers are flipped.

Reversing a singly linked list involves reassigning the next pointer of each node to point to its previous node instead of the next one.

Since singly linked lists do not have prev pointers, we must carefully use extra pointers while traversing to track the previous and next nodes during reversal.

Visual Example

Suppose we have the following singly linked list:

We want to reverse the list so that the order becomes 50 → 40 → 30 → 20 → 10.

Step-by-Step Reversal

1. Start with prev = null and current = head (10).
2. Step 1: current = 10
   Save next = 20, reverse the link (10 → null), move prev = 10, current = 20.
3. Step 2: current = 20
   Save next = 30, reverse link (20 → 10), move prev = 20, current = 30.
4. Step 3: current = 30
   Save next = 40, reverse link (30 → 20), move prev = 30, current = 40.
5. Step 4: current = 40
   Save next = 50, reverse link (40 → 30), move prev = 40, current = 50.
6. Step 5: current = 50
   Save next = null, reverse link (50 → 40), move prev = 50, current = null.

At the end, prev points to the new head of the reversed list, and current is null. Return prev as the new head.

Complete Pseudocode: Reverse a Singly Linked List

This pseudocode shows how to reverse a singly linked list in-place by manipulating the node pointers.

function reverse(head):
    prev = null
    curr = head

    while curr != null:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next

    return prev

Let’s understand each part of the code step by step.

function reverse(head):
    prev = null
    curr = head

Explanation: We initialize prev as null because the new tail will point to null. curr starts at the head of the list.

---

    while curr != null:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next

Explanation: We iterate through the list and reverse the direction of each link one by one. We use next to temporarily hold the next node before updating pointers.

---

    return prev

Explanation: After the loop, prev points to the new head of the reversed list, so we return it.

Singly Linked List Reverse Operation Examples

The following examples demonstrate how a singly linked list is reversed in-place by updating the next pointers of each node.

Initial List	Reversed List	Explanation
[10, 20, 30, 40]	[40, 30, 20, 10]	Each node's next pointer is reversed one by one while traversing the list. Final head becomes the previous tail.
[5, 15, 25]	[25, 15, 5]	The links between nodes are flipped. The last node becomes the new head.
[1]	[1]	Single-node list remains the same after reversal.
[]	[]	Empty list stays empty after reversal.

Time Complexity of Singly Linked List Reverse Operation

Reversal Case	Time Complexity	Explanation
Iterative Reversal	O(n)	We traverse the entire list once, updating each node’s next pointer. Each operation takes constant time.
Recursive Reversal	O(n)	The recursive approach also visits each node once, though it incurs additional call stack overhead.

Space Complexity of Singly Linked List Reverse Operation

Reverse Case	Space Complexity	Explanation
Iterative Reverse	O(1)	We reverse the list in-place using a constant number of pointers (like prev, curr, next). No additional space is needed.
Recursive Reverse	O(n)	Each recursive call adds a new frame to the call stack, leading to linear space usage proportional to the number of nodes.

Key Takeaways

• Reversing a singly linked list involves changing the direction of all next pointers.
• In the iterative approach, we use three pointers: prev, curr, and next to reverse the list in-place.
• The iterative reverse has a time complexity of O(n) and space complexity of O(1).
• A recursive reverse is elegant but uses O(n) space due to call stack frames.
• Always update the head pointer to point to the new first node after reversal.
• Reversing the list does not require any new node creation or deletion.