反转链表I 、II

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列节点组成，节点可以在运行时动态生成。
每个结点包括两个部分：

• 存储数据元素的数据域
• 存储下一个结点地址的指针域。

相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

例题

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 :::info 示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL ::: 进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

思路

迭代

用nxt记录下一个节点，cur表示当前节点，prev表示上一个节点。
不断遍历节点，将当前节点cur指向前一个结点prev，然后将cur/prev分别向后移动，直到cur为空。
最后返回prev即可。

var reverseList = function(head) {
    if(!head) return head
    let prev = null , curr = head
    while(curr){
        // 暂存当前节点的下一节点
        const nxt = curr.next
        // 当前节点指向上一节点
        curr.next = prev
        // 将上一节点往后移动到当前节点
        prev = curr
        // 将当前节点移动到下一节点
        curr = nxt
    }
    return prev
};

递归

采用递归的方法，即不断递归到链表的倒数第二个节点。
然后在回退时，将当前节点的下一个节点指向为当前节点。 :::info n_1→…→_nk−1→nk→nk+1→…→nm→∅
将 nk+1的下一个节点指向nk:
n_1→…→_nk−1→nk→nk+1←…←nm ::: 最后注意的是要将 n1的下一个节点设置为空，以防出现环。

var reverseList = function(head) {
    if (!head || !head.next) return head;
    let curHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return curHead;
};

92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 :::info 输入: 1->2->3->4->5->NULL, left = 2, right = 4
输出: 1->4->3->2->5->NULL :::

思路

找出需要反转的子链表的起点节点leftNode与终点节点rightNode；
然后还要记录leftNode的前一个节点pre，和rightNode的后一个节点curr。
对子链表进行反转后，拼接链表。
将pre节点指向rightNode，然后leftNode节点指向curr即可。

var reverseBetween = function(head, left, right) {
    const dummyNode = new ListNode(-1);
    dummyNode.next = head;
    let pre = dummyNode;
    // 来到 left 节点的前一个节点
    for (let i = 0; i < left - 1; i++) {
        pre = pre.next;
    }
    // 来到 right 节点
    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;
    // 反转链表的子区间
    reverse(leftNode);
    // 接回到原来的链表中
    pre.next = rightNode;
    leftNode.next = curr;
    return dummyNode.next;
};
function reverse(head) {
  let prev = null
  let cur = head
  while (cur) {
    let next = cur.next
    cur.next = prev
    prev = cur
    cur = next
  }
}