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

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) {
        // write code here

        // 使用容器做中转，要求：有序，如：队列

        // 算法的时间复杂度O(N)，额外空间复杂度O(N)

        // 1.处理特殊链表
        if(head == null || head.next == null || head.next.next == null) {
            // 如果该链表无结点、单节点、双节点，直接返回
            return head;
        }

        // 2.第一遍遍历链表，按照下标的奇数和偶数分别存入不同的Queue中
        Queue<ListNode> oddList = new LinkedList<>();
        Queue<ListNode> evenList = new LinkedList<>();
        ListNode cur = head;
        int i = 0;
        while (cur != null) {
            i++;
            if (i % 2 == 1) {
                // 奇数位置，放入oddList集合中
                oddList.add(cur);
            } else {
                // 偶数位置，放入evenList集合中
                evenList.add(cur);
            }
            cur = cur.next;
        }

        // 3.先后从两个LinkedList中取出数据，奇集合在前，偶集合在后
        ListNode oddHead = null;
        ListNode oddTail = null;
        ListNode evenHead = null;
        ListNode evenTail = null;
        // 3.1 构建奇数位置结点链表
        while(!oddList.isEmpty()) {
            ListNode oddCur = oddList.poll();
            // 注意！结点出队后应该让其next指向null，避免可能的错误
            oddCur.next = null;
            if(oddHead == null) {
                // 第一次尾插新结点
                oddHead = oddCur;
                oddTail = oddHead;
            } else {
                oddTail.next = oddCur;
                oddTail = oddCur;
            }
        }
        // 3.2 构建偶数位置结点链表
        while(!evenList.isEmpty()) {
            ListNode evenCur = evenList.poll();
            // 注意！结点出队后应该让其next指向null，避免可能的错误
            evenCur.next = null;
            if(evenHead == null) {
                // 第一次尾插新结点
                evenHead = evenCur;
                evenTail = evenHead;
            } else {
                evenTail.next = evenCur;
                evenTail = evenCur;
            }
        }

        // 4.把它们连到一起，返回
        oddTail.next = evenHead;
        return oddHead;
    }
}