What is the time complexity of reversing a singly linked list of n nodes in place?
Correct answer B. O(n)
Explanation
In-place reversal walks the list once with three pointers (previous, current and next), flipping each node's next link to point backwards. Every node is visited exactly once, so the time is O(n) and the extra space is O(1). It cannot be O(1) time because each of the n links has to change; quadratic time would arise only from a naive repeated-traversal approach.
Answer checked How we write and check questions
Discussion