Problem Description

You are given the head of a singly linked-list.

The positions of a linked list of length = 7 for example, can intially be represented as:

[0, 1, 2, 3, 4, 5, 6]

Reorder the nodes of the linked list to be in the following order:

[0, 6, 1, 5, 2, 4, 3]

Notice that in the general case for a list of length = n the nodes are reordered to be in the following order:

[0, n-1, 1, n-2, 2, n-3, ...]

You may not modify the values in the list’s nodes, but instead you must reorder the nodes themselves.

Example 1:

Input: head = [2,4,6,8]
Output: [2,8,4,6]

Example 2:

Input: head = [2,4,6,8,10]
Output: [2,10,4,8,6]

Constraints:

• 1 <= Length of the list <= 1000
• 1 <= Node.val <= 1000

Approach

Use a Stack and a Queue to store the nodes of the linked list. Then, iteratively pull nodes from the front (Queue) and the back (Stack) to reconstruct the reordered list. Finally, cap off the end of the newly formed list to prevent infinite cycles.

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public void reorderList(ListNode head) {
        Stack<ListNode> st = new Stack<>();
        Queue<ListNode> que = new LinkedList<>();
        ListNode temp1 = head;
        while(temp1 != null){
            st.push(temp1);
            que.add(temp1);
            temp1 = temp1.next;
        }
        ListNode newTemp = new ListNode(0);
        ListNode temp = newTemp;
        int totalNodes = st.size();
        
    
        for(int i = 0; i < totalNodes; i++){
            if(i % 2 == 0){
                temp.next = que.remove(); // Get from the front
            } else {
                temp.next = st.pop();     // Get from the back
            }
            temp = temp.next;
        }
        
        // 3. Crucial: Cap off the end of the list so it doesn't loop infinitely
        temp.next = null;
    }
}