Reorder a linked list
Filed under Microsoft
Free read 3 of 3Confirm that nodes must be rearranged in-place without altering their internal values, and understand how odd vs. even lengths are handled.
The question
Given the head of a singly linked list, reorder it to be: L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ... You may not modify the values in the list's nodes, only the nodes themselves.
Constraints
- The number of nodes in the list is in the range [1, 5 * 10^4].
- 0 <= Node.val <= 1000
Examples
- Input
- head = [1,2,3,4]
- Output
- [1,4,2,3]
- Why
- The nodes are reordered from ends to center: 1->4->2->3.
Approach
Confirm that nodes must be rearranged in-place without altering their internal values, and understand how odd vs. even lengths are handled.
Store all node references in an array, then reconstruct the list using two pointers from both ends of the array. This takes O(n) space.
Find the middle of the linked list using slow and fast pointers, reverse the second half of the list, and finally merge the two halves alternately.
Empty list, single-element list, and lists with only two elements.
Tips
- What they are testing: Test with odd and even length lists, single node lists, and two-node lists to ensure pointers do not cause cycles.
- Common mistake: Failing to properly break the link between the first and second halves of the list, resulting in an infinite cycle.
Related Microsoft questions
Collected from public candidate posts and coding forums. Updated Nov 2026.