Interleave the first half of a queue with the second half
Problem
Given a queue of even length, interleave its first half with its second half: first[0], second[0], first[1], second[1], …
Example 1
Input: [11, 12, 13, 14, 15, 16, 17, 18, 19, 20] Output: [11, 16, 12, 17, 13, 18, 14, 19, 15, 20]
Also asked as: Interleave the first half of the queue with second half
Test cases
Case 1
Input: [11,12,13,14,15,16,17,18,19,20] Expected: [11,16,12,17,13,18,14,19,15,20]
Case 2
Input: [1,2,3,4] Expected: [1,3,2,4]
Case 3
Input: [1,2] Expected: [1,2]
Case 4
Input: [] Expected: []
View solutionHide solution1 approach
1. Move first half to a stack, re-queue, then interleave
Time O(n)Space O(n)
Push the first n/2 to a stack, enqueue back (now the front half is reversed and rotated), rotate n/2, then alternately pull from stack-equivalent and queue.
function interleaveQueue(q) { const half = q.length / 2; const st = []; for (let i = 0; i < half; i++) st.push(q.shift()); while (st.length) q.push(st.pop()); for (let i = 0; i < half; i++) q.push(q.shift()); for (let i = 0; i < half; i++) { st.push(q.shift()); } const res = []; for (let i = 0; i < half; i++) { res.push(st.pop()); res.push(q.shift()); } q.push(...res); return q;}