Q8: How do you reverse a Singly LinkedList iteratively in O(n) time and O(1) space?
Maintain three pointers: prev (initialized to null), curr (initialized to head), and next. Traverse the list: store curr.next in next, reverse curr.next to point to prev, advance prev to curr, and advance curr to next. Return prev as the new head.
Iterative LinkedList Reversal
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public class ReverseLinkedList {
public static ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
}💡 Rebinds pointer targets step-by-step until the list traversal completes.
Key Takeaways
- Use
prev,curr, andnextpointers to reverse node pointers in place. - $O(n)$ time complexity, $O(1)$ space complexity.
Knowledge Check
What does the prev pointer point to at the conclusion of the iterative reversal loop?