2021/03/18 每日一题 反转链表 II

LeetCode上反转链表 II，中等难度，参考了官方题解，记录下解题思路

给一个链表，并且给与left和right两个参数，其中left <= right，需要翻转[left,right]内的链表节点，并且返回链表
假设链表为1,2,3,4,5，left = 2,right = 4

1. 遍历[0,left]区间，确认pre的具体位置
2. 遍历[left,right - left + 1]区间，确认next的位置
   
   
   把需要翻转的链表截取出来，并且切断pre和next与这个链表的联系
   之后翻转链表，反转链表可以参考LeetCode刷题 反转链表，反转完成后重新连接即可
   

var reverseBetween = function(head, left, right) {
    // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
    const dummyNode = new ListNode(-1);
    dummyNode.next = head;
    let pre = dummyNode;
    // 确认正确的pre
    for (let i = 0; i < left - 1; i++) {
        pre = pre.next;
    }
    // 确认正确的next
    let rightNode = pre;
    for (let i = 0; i < right - left + 1; i++) {
        rightNode = rightNode.next;
    }
    // 获取要交换的链表
    let leftNode = pre.next;
    let curr = rightNode.next;
    // 切断链接
    pre.next = null;
    rightNode.next = null;
    // 翻转链表
    reverseLinkedList(leftNode);
    // 重新拼接
    pre.next = rightNode;
    leftNode.next = curr;
    return dummyNode.next;
};
const reverseLinkedList = (head) => {
    let pre = null;
    let cur = head;
    while (cur) {
        const next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
}