题解 | #重排链表#

 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 * 
 * @param head ListNode类 
 * @return void
 */
function reorderList( head ) {
    // write code here
    if(!head || !head.next||!head.next.next){
        return head
    }
    let fast = head,slow = head
    while(fast && fast.next && fast.next.next){
        fast = fast.next.next
        slow = slow.next
    }
    let res = reverse(slow.next)
    slow.next = null
    let ans = head,p1 = ans,p2 = res
    while(ans && res){
        p1 = ans.next
        p2 = res.next
        ans.next = res
        res.next = p1
        ans = p1
        res = p2
    }
    return head
}
function reverse(head){
    let cur = null
    let pre = null
    while(head){
        cur = head.next
        head.next = pre
        pre = head
        head = cur
    }
    return pre
}

module.exports = {
    reorderList : reorderList
};

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 * 
 * @param head ListNode类 
 * @return void
 */
function reorderList( head ) {
    // write code here
    if(!head || !head.next||!head.next.next){
        return head
    }
    let arr = []
    while(head){
        arr.push(head)
        head = head.next
    }
    let i = 0,j = arr.length - 1
    while(i < j){
        arr[i].next = arr[j]
        i++
        if(i===j)    break
        arr[j].next = arr[i]
        j--
    }
    arr[i].next = null
    return arr[0]
}
module.exports = {
    reorderList : reorderList
};