Reverse Linked List

How it works

Reversing a linked list iteratively is all about flipping pointers one step at a time. We walk through the list from left to right, and for each node, we redirect its next pointer to point to the node behind it.

To avoid losing track of the rest of the list, we keep three pointers:

• curr → the current node we are processing
• prev → the node that should come after curr once reversed
• temp → the original next node (so we don't break the chain)

By moving these pointers forward in each step, we gradually reverse the entire list. When curr becomes null, the list is fully reversed, and prev points to the new head.

Steps

1. Initialize:
   • prev = null
   • curr = head
2. While curr exists:
   • Save the next node: temp = curr.next
   • Reverse the pointer: curr.next = prev
   • Move prev to curr
   • Move curr to temp
3. When the loop ends, prev is the new head of the reversed list.
4. Return prev.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Losing the Reference to the Next Node

When reversing a linked list iteratively, you must save the next node before modifying the current node's pointer. A common mistake is writing curr.next = prev before storing curr.next in a temporary variable, which causes you to lose access to the rest of the list and breaks the traversal.

Forgetting to Set the Original Head's Next to Null

In the recursive approach, after reversing the rest of the list, the original head becomes the new tail. Forgetting to set head.next = null creates a cycle in the list, where the last two nodes point to each other, leading to infinite loops when traversing the reversed list.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev, curr = None, head

        while curr:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        return prev

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;

        while (curr) {
            ListNode* temp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }
};