Can we reverse a linked list in less than O(n)? / Why quicksort for arrays, merge sort for lists?
Problem
Two conceptual questions. (1) Can a singly linked list be reversed faster than O(n)? (2) Why is quicksort preferred for arrays but merge sort for linked lists? Answer each with the reasoning an interviewer expects.
Also asked as: Can we reverse a linked list in less than O(n) ? · Why Quicksort is preferred for. Arrays and Merge Sort for LinkedLists ?
Test cases
No automated tests for this problem yet. Use the examples above to check your output.
This problem has no automated tests. Run executes your code and shows what it logs.
View solutionHide solution1 approach
1. Conceptual answers
Time —Space —
No — reversing requires visiting every node to flip its pointer, so it is Θ(n). For sorting: arrays give O(1) random access and cache locality, which quicksort exploits and merge sort wastes (its O(n) auxiliary array + copying hurt). Linked lists have no random access, so quicksort’s partition is awkward and pivots are hard to pick; merge sort splits and merges with only pointer rewiring and O(1) extra space, and is stable — hence the default for lists.
// Reversal is O(n): every node's next pointer must change.// Merge sort on a list needs no random access and O(1) extra space;// quicksort on a list can't pick a good pivot cheaply and loses locality.