Reorder List
Medium · Linked List
You are given the head of a singly linked list. Rearrange its nodes in place so the sequence alternates by taking the first remaining node, then the last remaining node, then the next first remaining node, then the next last remaining node, and so on, weaving from both ends toward the middle. Do not create new nodes or return anything; modify the existing list's links directly so it holds the new order.
Examples
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Why: The first node stays first, then the last node is inserted, then the second node, then the second-to-last, weaving inward.Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Why: Weaving from both ends toward the middle gives 1,5,2,4,3.Input: head = [1]
Output: [1]
Why: A single node has nothing to reorder.Constraints
1 <= list length <= 5*10^4, -1000 <= node value <= 1000
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Reorder List. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.