Interleave the First Half of the Queue with Second Half

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Interleave first half of queue with second half: [1,2,3,4,5,6] -> [1,4,2,5,3,6].

Algorithm

1Push first half into stack. Enqueue stack elements alternated with second-half dequeues.

Common Pitfalls

•Use stack for first half reversal. Then interleave: dequeue second-half element, enqueue first pair, repeat.

Interleave the First Half of the Queue with Second Half.java

Java

// Approach: Split into two stacks/queues and interleave elements alternately.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    public void rearrangeQueue(Queue<Integer> q) {
        List<Integer> list = new ArrayList<>();
        boolean isRev = false;

        while (!q.isEmpty()) {
            int mid = q.size() / 2;

            if (isRev) {

                list.add(q.poll());
                mid--;

                while (mid-- > 0)
                    q.add(q.poll());

                list.add(list.size() - 1, q.poll());
            } else {
                list.add(q.poll());
                mid--;
                while (mid-- > 0)
                    q.add(q.poll());

                list.add(q.poll());
            }

            isRev = !isRev;
        }
        for (int v : list)
            q.add(v);
    }
}

Was this solution helpful?