题解 | #重排链表#

    public void reorderList(ListNode head) {
        if(head==null||head.next==null) return;
        //1.找上中点
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //slow去到中点或者上中点，后半段就是slow的下一个节点牵头
        ListNode next = slow.next;
        slow.next = null;
        //2.后半段链表反转
        next = reverseList(next);
        //3.两端merge起来
        head = merge(head,next);
    }
    public ListNode reverseList(ListNode cur){
        ListNode pre = null;
        ListNode next;
        while(cur!=null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    //这里的merge是先list1再list2,彼此交替
    public ListNode merge(ListNode list1,ListNode list2){
        ListNode res = new ListNode(0);
        ListNode tail = res;
        boolean isList1 = true;
        while(list1!=null&&list2!=null){
            tail.next = isList1?list1:list2;
            if(isList1){
                list1 = list1.next;
            }else{
                list2 = list2.next;
            }
            isList1 = !isList1;
            tail = tail.next;
        }
        if(list1!=null){
            tail.next = list1;
        }
        if(list2!=null){
            tail.next = list2;
        }
        return res.next;
    }