GATE CS 2022 Q5 — Linked Lists

To reverse a singly linked list of size $n$ in-place (using $O(1)$ auxiliary space), we can use an iterative approach with three pointers: prev, curr, and next.

Iterative Algorithm:

1. Initialize three pointers: prev = NULL, curr = head, and next = NULL.
2. Iterate through the linked list until curr is NULL:
   • Store the next node: next = curr->next
   • Reverse the current node's pointer: curr->next = prev
   • Move pointers one step forward: prev = curr, curr = next
3. Set the head of the reversed list: head = prev.

Complexity Analysis:

• Time Complexity: The algorithm traverses the list of $n$ nodes exactly once. At each node, it performs a constant number of pointer updates. Thus, the worst-case time complexity is $\theta(n)$.
• Space Complexity: The algorithm only uses three extra pointer variables, which requires $O(1)$ auxiliary space.

Since we can successfully reverse the list in $\theta(n)$ time and $O(1)$ space, Option A is the correct statement.