题解 | #链表的奇偶重排#双指针｜借助队列

解法1: 双指针交替

指针odd和even相互只想对方的下一个节点以构造对应的链，最后可以得到odd链和even链，再让odd链的尾节点指向even链的头节点

需要注意边界条件，也就是退出while循环的条件，可以分两个case来考虑： 链表节点为奇数时，链表节点为偶数时

当链表节点为奇数时，even == null时退出：

当链表节点为偶数时，even.next == null时退出：

最后再让odd.next指向evenHead;

import java.util.*;
public class Solution {
    public ListNode oddEvenList (ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        ListNode odd = head;
        ListNode evenHead = head.next;
        ListNode even = odd.next;
        while(even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next; 
            even = odd.next;
        }
        odd.next = evenHead;
        return head;
    }
}

解法2：借助队列

把奇数位的节点放到队列oddNode里面

把偶数位的节点放到队列evenNodes里面

然后将队列的元素依次出队构建链表，先出oddNodes，再出evenNodes

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param head ListNode类
     * @return ListNode类
     */
    //借助队列
    public ListNode oddEvenList (ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        Queue<ListNode> oddNodes = new LinkedList<ListNode>();
        Queue<ListNode> evenNodes = new LinkedList<ListNode>();
        ListNode odd = head;

        while (odd != null && odd.next != null) {
            oddNodes.add(odd);
            evenNodes.add(odd.next);
            odd = odd.next.next;
        }
        if (odd != null) {
            oddNodes.add(odd);
        }

        ListNode current = oddNodes.poll();
        while (oddNodes.size() != 0) {
            current.next = oddNodes.poll();
            current = current.next;
        }
        while (evenNodes.size() != 0) {
            current.next = evenNodes.poll();
            current = current.next;
        }
        current.next = null;
        return head;
    }
}