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

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) {
        //方法1
        return oddEvenList1(head);
//         //方法二
//         return oddEvenList2(head);
//         //方法三
//         return oddEvenList3(head);
    }
    
    //空间复杂度o(n),时间o(n)
    //遍历存入两个队列，最后拼装
    public ListNode oddEvenList1 (ListNode head) {
        if(head==null||head.next==null){
            return head;
        }

        ArrayList<ListNode> jilist= new ArrayList<ListNode>();
        ArrayList<ListNode> ouList = new ArrayList<ListNode>();
        ListNode pre=null,cur=head;
        boolean ji=true;
        while(cur!=null){
            if(ji){
                jilist.add(cur);
                ji=false;
            }else{
                ouList.add(cur);
                ji=true;
            }
            cur=cur.next;
        }
        
        for(ListNode temp:jilist){
            if(pre==null){
                pre= temp;
                head = pre;
            }else{
                pre.next=temp;
                pre = temp;
            }
        }
        
        for(ListNode temp:ouList){
            pre.next=temp;
            pre = temp;
        }
        pre.next=null;
        return head;
    }
    
    
    //空间复杂度o(1),时间o(n)
    //遍历直接改成两个链表，最后拼装
    public ListNode oddEvenList2 (ListNode head) {
        ListNode cur,next,pre=null,ouhead,ounext,oupre;
        if(head==null||head.next==null){
            return head;
        }
        ouhead=head.next;
        ounext = ouhead;
        oupre = ouhead;
        cur = head;
        boolean first=true;
        //判断条件为奇数
        while(cur!=null&&cur.next!=null){
            if(!first){
                oupre.next=cur.next;
            }
            ounext=cur.next;
            cur.next = ounext.next;
            pre= cur;
            oupre= ounext;
            cur = ounext.next;
            first=false;
        }
		oupre.next=null;
        if(cur!=null){
            cur.next=ouhead;
        }else{
            pre.next=ouhead;
        }
        return head;
    }
    
    //与2类似，网上简略写法，用偶数链当判断条件
    public ListNode oddEvenList3 (ListNode head){
        if(head==null) return  head;
       //无需对头节点做操作 不用dummyHead
        //奇链表头位于head 偶链表头位于head.next
        ListNode oddHead = head,evenHead = head.next;
        ListNode odd = oddHead,even = evenHead;
        //终止条件：因为even走在前面 一定先终止 所以判断条件就是它
        //节点总数为偶数个时 even.next为null
        //节点总数为奇数个时： even==null  这俩条件触发一个就跳出循环
        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;
    }
}