143.重排链表

function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
}
/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
// 长度为n的链表
// 重排后 L0 → Ln-1 → L1 → Ln - 2 → L2 → Ln - 3 → …
var reorderList = function (head) {
    // 先把节点用数组存起来，方便拿取
    let arr = []

    let cur = head
    while (cur) {
        arr.push(cur)
        cur = cur.next
    }
    // console.log(arr)

    // 开始重排
    // 只需要遍历len/2次就行，因为有一半的节点会从后面插入到前面
    let len = arr.length
    let half = Math.floor(len / 2)
    for (let i = 0; i < half; i++) {
        console.log(arr[i])
        arr[i].next = arr[len - 1 - i]
        arr[len - 1 - i].next = arr[i + 1]
    }
    // 最后一个指向null，否则就变成环形链表
    arr[half].next = null

    return head
};

/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function (head) {
    // 注意到目标链表是由 左半端节点 和 反转后的右半端节点 错位合并的结果
    // 1.找到链表的中间点，把链表分成左右两半
    // 2.对右半端子链进行反转
    // 3.左半端子链和反转后的右半端子链进行错位合并

    if (!head || !head.next) {
        return head
    }

    // 获取中间节点
    let middle = getMiddleNode(head)

    // 将链表分割成左右子链
    let [left, right] = divideLeftAndRight(head, middle)

    // 反转右半端子链
    let reversedRight = reverseNodes(right)

    // 左半端子链和反转的右半端子链 错位合并
    head = merge(left, reversedRight)

    return head
}

/**
 * 获取链表中间节点
 * @param {ListNode} head 
 */
function getMiddleNode(head) {
    // 可以巧妙的使用快慢指针，快指针一次两步，慢指针一次一步
    // 2slow = fast，等fast访问到链尾，slow刚好访问到中点
    let slow = head
    let fast = head
    while (slow && fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
}

/**
 * 将链表按中间节点分割成左右子链
 * @param {ListNode} head 
 * @param {ListNode} mid 
 */
function divideLeftAndRight(head, middle) {
    let cur = head
    while (cur.next !== middle) {
        cur = cur.next
    }
    // 左子链尾巴置为null，和右子链断开
    cur.next = null

    let left = head
    let right = middle
    return [left, right]
}

/**
 * 反转链表
 * @param {ListNode} head 
 */
function reverseNodes(head) {
    let pre = null
    let cur = head
    while (cur) {
        let next = cur.next
        cur.next = pre

        pre = cur
        cur = next
    }
    return pre
}

/**
 * 错位合并两个链表
 * @param {ListNode} head1 
 * @param {ListNode} head2 
 */
function merge(head1, head2) {
    let l1 = head1
    let l2 = head2
    // console.log(head1)
    // console.log(head2)

    // 因为按中点分割，head2长度肯定大于等于head1
    while (l1) {
        let l1Next = l1.next
        let l2Next = l2.next
        l1.next = l2
        // l2比l1长
        if (l1Next) {
            l2.next = l1Next
        }

        l1 = l1Next
        l2 = l2Next
    }
    return head1
}


function print(head) {
    let res = []
    let cur = head
    while (cur) {
        res.push(cur.val)
        cur = cur.next
    }
    console.log(res)
}

const head = new ListNode(1)
const n1 = new ListNode(2)
const n2 = new ListNode(3)
const n3 = new ListNode(4)
const n4 = new ListNode(5)
head.next = n1
n1.next = n2
n2.next = n3
n3.next = n4
print(head)
// console.log('mid', getMiddleNode(head))
// const reverHead = reverseNodes(head)
// print(reverHead)

const newHead = reorderList(head)
print(newHead)
# 143.重排链表

143.重排链表
