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

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
        // 解题思路:
        // 1.如果链表为空或者链表只有一个节点，则返回head
        // 2.新建2个链表(n1,n2)分别代表奇/偶
        // 3.遍历链表,i从1开始,i%2== 0 则为偶节点 加到n2的后面，否则为奇数节点加到n1的后面
        // 4.注意：如果链表节点数是偶数，则2个节点都可以遍历到最后
        // 如果是奇数个数，则偶数节点的最后一个节点需要清空
        if (head == null || head.next == null) {
            return head;
        }

        int i = 1;
        ListNode n1 = new ListNode(-1);
        ListNode c1 = n1;
        ListNode n2 = new ListNode(-1);
        ListNode c2 = n2;

        while (head != null) {
            if (i % 2 == 0) {
                c2.next = head;
                c2 = c2.next;
            } else {
                c1.next = head;
                c1 = c1.next;
            }

            i++;
            head = head.next;
        }

        if (i % 2 == 0) {
            c2.next = null;
        }

        c1.next = n2.next;

        return n1.next;
    }
}