LeetCode328. 奇偶链表

思路1：类似LeetCode86. 分隔链表，设置两个虚拟头节点，最后拼接即可。

☆☆思路2：分离节点后合并，不需要设置虚拟头节点

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;
        /**
         *  方法1：设置两个虚拟头节点
         */
        /*
        ListNode dummyHead1 = new ListNode(0);
        ListNode dummyHead2 = new ListNode(0);
        ListNode node1 = dummyHead1;
        ListNode node2 = dummyHead2;
        int cnt = 1;
        while (head != null) {
            if ((cnt & 1) == 1) {
                node1.next = head;
                node1 = node1.next;
            }else {
                node2.next = head;
                node2 = node2.next;
            }
            head = head.next;
            cnt ++;
        }
        node2.next = null;
        node1.next = dummyHead2.next;
        return dummyHead1.next;
        */
        /**
         * 方法2：不需要设置虚拟头节点
         */
        ListNode evenHead = head.next; // 偶数链表的头节点
        ListNode odd = head, even = head.next;
        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}