Discussion
Consider the problem of reversing a singly linked list. To take an example, given the linked list below,
head → a → b → c → d → e → (null)
the reversed linked list should look like
head → e → d → c → b → a → (null)
Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in \(O(1)\) space?
Answer: A
The best algorithm takes \(\theta(n)\) time in the worst case.
The standard in-place reversal walks the list once with three pointers (previous, current, next), turning each node's next pointer around as it passes. It uses a constant number of extra pointers, so \(O(1)\) space, and does constant work per node, so \(O(n)\) time.
No algorithm can do better, because every one of the \(n\) next pointers must change, which already needs \(\Omega(n)\) steps. So \(\theta(n\log n)\) and \(\theta(n^{2})\) overstate the cost of the best algorithm, and the claim that reversal is impossible in \(O(1)\) space is refuted by the three-pointer method.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development