# 链表相关算法题

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let prev = null,
        cur = head;
    while (cur != null) {
        const next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    // 反转后的头节点就是prev
    return prev;
}

var reverseBetween = function(head, m, n) {

    // 判空
    if (head == null) return null;

    // 移动两个指针prev, cur到n的位置
    let prev = null,
        cur = head;
    while (m > 1) {
        prev = cur;
        cur = cur.next;
        // 索引矫正
        m--;
        n--;
    }

    // 更新前两个指针
    const con = prev,
        tail = cur;
    // 两个指针位置调整好了，所以现在就相当于已经将0, n-m范围的链表反转了
    let temp = null;
    while (n > 0 && cur != null) {
        temp = cur.next;
        cur.next = prev;
        prev = cur;
        cur = temp;
        n--;
    }

    // 调整最终的链接
    if (con != null) {
        con.next = prev;
    } else {
        // 反转过后,prev就是头节点
        head = prev;
    }
    tail.next = cur;
    return head;

}

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val; 
 *     this.next = null; 
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var deleteNode = function(head, val) {

    // 哨兵节点
    const pre = new ListNode(-1);
    pre.next = head;
    let temp = pre;
    while (temp.next != null) {
        // 找出要删除的节点
        if (temp.next.val === val) {
            // 将下个节点的指针指向下下个节点
            temp.next = temp.next.next;
            break;
        }
        // 指针前进
        temp = temp.next;
    }
    return pre.next;
}

var reversePrint = function(head) {

    if (head == null) return [];
    // 反转链表
    head = reverseList(head);
    // 存放每个链表节点元素
    const res = [];
    while (head != null) {
        head.val != null && res.push(head.val);
        // 指针前进
        head = head.next;
    }
    return res;

}
// 反转链表
var reverseList = function(head) {

    let prev = null,
        curr = head;
    while (curr != null) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;

}

var reversePrint = function(head) {

    if (head == null) return [];
    const res = [];
    while (head != null) {
        // 头部插入
        head.val != null && res.unshift(head.val);
        // 指针前进
        head = head.next;
    }
    return res;

}

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val; 
 *     this.next = null; 
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {

    // 哨兵节点
    const pre = new ListNode(-1);
    let temp = pre;
    while (l1 != null && l2 != null) {
        const val1 = l1 ? l1.val : 0;
        const val2 = l2 ? l2.val : 0;
        if (val1 < val2) {
            // l1的节点值比l2小，下个节点的指针指向l1
            temp.next = l1;
            // l1指针前进
            l1 = l1.next;
        } else {
            // 同上
            temp.next = l2;
            l2 = l2.next;
        }
        // temp指针前进到下一步
        temp = temp.next;
    }
    // 循环完毕后，l1或者l2还有剩余的节点，直接 接在下个节点的指针就可以
    temp.next = l1 != null ? l1 : l2;
    return pre.next;

}

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val; 
 *     this.next = null; 
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {

    if (head == null) return null;
    // 存放链表的每个节点
    const result = [];
    let node = null;
    while (head != null) {
        result.push(head);
        // 指针前进
        head = head.next;
    }
    while (k--) {
        // 倒数第k个节点，就是对应从后往前第k个
        node = result.pop();
    }
    return node;

}

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val; 
 *     this.next = null; 
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {

    // 只要有一个空节点，那就是没有公共节点，直接返回空
    if (headA == null || headB == null) return null;
    let temp = headA,
        lengthA = 0,
        lengthB = 0;
    // 1. 计算链表headA的长度
    while (temp != null) {
        lengthA++;
        temp = temp.next;
    }

    temp = headB;
    while (temp != null) {
        lengthB++;
        temp = temp.next;
    }

    // 2. 计算两个链表的长度差，声明快慢两个指针, 当两个指针相遇了(一样)，就是公共节点
    let diff = Math.abs(lengthA - lengthB),
        slow = null,
        fast = null;
    if (lengthA < lengthB) {
        // 链表长度长，说明要走更多的路，就是慢指针，反之就是快指针
        slow = headB;
        fast = headA;
    } else {
        slow = headA;
        fast = headB;
    }

    // 3. 慢指针前进diff步，保证由相遇的可能性
    while (diff--) {
        slow = slow.next;
    }

    // 4. 两个指针再一起前进, 直到相遇
    while (slow !== fast) {
        slow && (slow = slow.next);
        fast && (fast = fast.next);
    }

    // while循环后，说明相遇了，随便一个就是公共节点
    return slow;

}

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val; 
 *    this.next = next; 
 *    this.random = random; 
 * }; 
 */

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function(head) {

    if (head == null) return null;
    let node = head; // 表示当前节点
    const newHead = new Node(head.val);
    const map = new Map();
    let newNode = newHead;
    // 当前节点到新节点的映射关系
    map.set(node, newNode);

    // 1. 复制next指针
    while (node.next != null) {
        newNode.next = new Node(node.next.val);
        // 当前节点指针前进
        node && (node = node.next);
        // 新节点指针前进
        newNode = newNode.next;
        // 继续存入当前节点到新节点的映射
        map.set(node, newNode);
    }

    // 2. 全部回到头节点
    newNode = newHead;
    node = head;

    // 3. 复制random指针
    while (newNode != null) {
        newNode.random = map.get(node.random);
        // 指着前进
        newNode = newNode.next;
        node && (node = node.next);
    }

    // 返回新的链表
    return newHead;

};

/**
 * // Definition for a Node.
 * function Node(val, left, right) {
 *    this.val = val; 
 *    this.left = left; 
 *    this.right = right; 
 * }; 
 */
/**
 * @param {Node} root
 * @return {Node}
 */
var treeToDoublyList = function(root) {

    if (root == null) return;
    let head = null,
        pre = head;
    // 中序遍历
    function inorder(node) {
        if (node == null) return;
        // 遍历左子树
        inorder(node.left);
        if (pre != null) pre.right = node; // 指向下个节点
        else head = node; // 说明是头节点(遍历到最左边节点，此时节点就是双向链表的head)
        node.left = pre;
        // 指针前进
        pre = node;
        // 遍历右子树
        inorder(node.right);
    }
    // 中序遍历后, pre指向了最后一个节点
    inorder(root);
    head.left = pre;
    // 最后一个节点的后继指针指向头节点，这样就形成了环链表
    pre.right = head;
    return head;
}