Reorder a Linked List
Rearrange a singly-linked list by alternating nodes from the front and the back until they meet in the middle.
You are given the head of a singly-linked list containing n nodes, labeled L0 through Ln-1 in their original order.
Reorder the nodes of the list so that they appear in the following interleaved order:
L0, Ln-1, L1, Ln-2, L2, Ln-3, ...In other words, repeatedly take the next unused node from the front of the original list, then the next unused node from the back, until every node has been placed.
Return the values of the list in this new order.
Example 1
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Example 2
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Example 3
Input: head = [1]
Output: [1]
Explanation: A list with a single node is already in its reordered form.
Constraints
- The number of nodes in the list is in the range [0, 5 * 10^4].
- -1000 <= Node.val <= 1000
Follow-up
Can you solve it using only O(1) extra space beyond the list's own nodes, without allocating a second list?
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.