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

import java.util.LinkedList;

/*
 * 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) {
        // write code here
        if (null == head) {
            return null;
        }
        if (null == head.next) {
            return head;
        }
        // 具体代码实现
        // 定义一个队列，用于存放链表中的奇数位节点
        LinkedList<ListNode> oddQue = new LinkedList<>();
        // 定义一个队列，用于存放链表中的偶数维位节点
        LinkedList<ListNode> evenQue = new LinkedList<>();
        // 定义一个辅助指针，用于指向当前链表中遍历的位置
        ListNode tp = head;
        // 定义一个整型变量，用于表明当前位置是奇数位还是偶数位
        int val = 1;
        while (null != tp) {
            if (val % 2 == 0) { // 偶数位
                evenQue.add(tp);
                tp = tp.next;
                val++;
            }
            else { // 奇数位
                oddQue.add(tp);
                tp = tp.next;
                val++;
            }
        }
        // 先遍历oddQue，再遍历evenQue
        head = oddQue.poll();
        tp = head;
        while (!oddQue.isEmpty()) {
            tp.next = oddQue.poll();
            tp = tp.next;
        }
        while (!evenQue.isEmpty()) {
            tp.next = evenQue.poll();
            tp = tp.next;
        }
        tp.next = null;
        // 返回结果
        return head;
    }
}