题解 | #链表的奇偶重排#

思路：考虑使用两个辅助队列，构造新链表

1. 一次遍历链表，将奇数节点值依次入队q1，偶数节点值依次入队q2
2. 依次将q1中节点值出队，构造新节点，接在新链表后面。然后q2中节点值出队，构造新节点，接在新链表后面
3. 最后返回新链表头节点

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode oddEvenList (ListNode head) {
        // 思路：两个队列 （q1中放奇数节点，q2中放偶数节点），然后先将q1依次出队，放在新链表后面，再将q2依次出队，放在后面
        Queue<Integer> q1 = new LinkedList<>(); // 存放奇数节点值的队列
        Queue<Integer> q2 = new LinkedList<>(); // 存放偶数节点值的队列
        ListNode node = new ListNode(-1); // 虚拟头节点
        ListNode newNode = node;
        int index = 1; // 节点计数
        while(head != null){
            if(index % 2 != 0){ // 奇数节点值入队q1
                q1.offer(head.val);
            }else{ // 偶数节点值入队q2
                q2.offer(head.val);
            }
            index++;
            head = head.next;
        }
        while(!q1.isEmpty()){ // q1中节点值出队
            node.next = new ListNode(q1.poll());
            node = node.next;
        }
        while(!q2.isEmpty()){ // q2中节点值出队
            node.next = new ListNode(q2.poll());
            node = node.next;
        }
        return newNode.next;
    }
}