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

思路：前提 如果 head的长度小于2 直接返回 [1 2 3 4 5 6] n1 = [1] n2 = [2] p = n1, pre = n2; 计数 如果num % 2 == 1 代表是奇数节点 则开始拼接

1. [1] -> [3]
2. [2] -> [4]

循环，呆到下一个奇数节点，

1. [3] -> [5]
2. [4] -> [6]

最后 p.next = n2 拼接

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
        if(head == null || head.next == null || head.next.next == null) {
            return head;
        }
        ListNode n1 = head;   //1
        ListNode n2 = head.next; //2
        ListNode pre = n2;//2
        ListNode p = head.next.next;//3
        n1.next = p;//1 -> 3
        ListNode q = n1;
        int i = 1;
        
        while(p != null) {
            if(i % 2 == 1) {
                q.next = p;//尾插 将奇数节点插入到n1
                q = p;
                
                pre.next = q.next;//拼接n2
                p = q.next;// 记录下一个节点 保证p遍历链表不断
                i++;//因为p = q.next 所以i++ 保证计数准确
                q.next = null;//让奇数链表每一次插入都只插入一个奇数节点，保证最后 1->3->5 而不是 1->3->5->6 因为最后一个数如果是偶数节点，则无法进入这个if
            } else {
                i++;
                pre = p;//保证偶数链表，准确连接
                p = p.next;
            }
           
        }
        q.next = n2;//拼接
        return n1;
    }
}