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

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、遍历链表 当i%2 == 0 说明是偶数，便放进偶数的链表里
        // 否则是奇数，则放进奇数的链表里
        // 遍历完之后记得把偶数链表的最后一个元素的next清空，因为它后面可能还有其他节点
        // 最后把奇数链表的next 指向偶数链表
        if(head == null || head.next == null){
            return head;
        }
        int i=1;

        ListNode oNode = new ListNode(-1);
        ListNode oCur = oNode;
        ListNode jNode = new ListNode(-1);
        ListNode jCur = jNode;

        while(head != null){
            // 偶数位
            if(i %2 ==0){
                oCur.next = head;
                oCur = oCur.next;
            }else{
                jCur.next = head;
                jCur = jCur.next;
            }

            i++;
            head = head.next;
        }
        // 把偶数链表的next清空，因为后面可能还有节点
        oCur.next = null;
        jCur.next = oNode.next;

        return jNode.next;
    }
}