143.重排链表——medium

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reorder-list

思路：
使用快慢指针找到链表中点，然后翻转后半个链表，将两部分链表合并
复杂度分析：
时间复杂度O(n)
空间复杂度O(1)

var reorderList = function(head) {
    if(!head)return null;
    const merge = (l1,l2)=>{
        let l1_tmp,l2_tmp;
        while(l1 && l2){
            l1_tmp = l1.next;
            l2_tmp = l2.next;
            l1.next = l2;
            l1 = l1_tmp;
            l2.next = l1;
            l2 = l2_tmp;
        }
    }
    const reverse = (head)=>{
        let pre;
        let cur = head;
        while(cur){
            let next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    const getMid = (head)=>{
        let fast = head;
        let slow = head; 
        while(slow.next &&fast.next&&fast.next.next ){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    let l1 = head;
    let mid = getMid(head);
    let l2 = mid.next;
    mid.next = null;
    l2 = reverse(l2);
    merge(l1,l2);
    return l1;
};