迭代-移动结点式反转

1、如果只需反转单链表中的一部分呢？如反转单链表的m-n区间
使用迭代的方式在顺向迭代反转的时候，链表反转的结点处理和上面的顺向遍历时修改指向略微不一样

顺向遍历时修改指向解法图示：

由于这种改变反转的方式，在链尾时才能完全反转，在实现反转的中途链表是混乱的，甚至是断开的。如果要在这个算法思路上改造适合指定区间的反转，需要在反转指定区间后，额外处理头结点的指向、已反转链表与原链表的焊接的问题，改造代价略高。

我们换一种反转的操作思路，从而实现指定区间的反转：

输入 1->2->3->4->5->null m=2，n=3
期望 1->4->3->2->5->null

下面是该算法的处理过程：

该算法从“移动”结点的角度出发，通过断链、改变指向的方式实现了结点的移动，核心是head结点指向永远不变，head的next结点不断移动(交换)到指定反转区域的首部，head结点不断往后移，head.next不断往前移，中间保持其他结点的相对位置，从而实现反转。

以1->2->3->4->5->6->null, n=2,m=5为例，链表变化过程如下

完整代码如下：

function reverseBetween(head, m, n) {
    let dummy = new ListNode();
    dummy.next = head;
    let prev = dummy;
    // head指向m所在结点，prev指向head前的结点
    for (let i = 1; i < m; i++) {
        prev = prev.next;
    }
    head = prev.next;
    // 开始反转
    // 我们需要反转n-m次，head结点指向永远不变，head的next结点不断移动(交换)到指定反转区域的首部
    for(let i=m; i<n; i++) {
        // 注意顺序
        let next_temp = head.next;
        head.next = next_temp.next;
        next_temp.next = prev.next;
        prev.next = next_temp;
    }
    return dummy.next;
}

递归-从函数定义上理解

回顾反转链表里的递归解法（点我），我们当时是以回溯的思想来思考的，我们将当递归到达base出口弹栈的过程理解为反向遍历，在弹递归栈的时候实现了反转。
反转链表-指定区间 - 图4

同样的代码，我们试试从递归函数定义的角度上理解

funciton reverse(ListNode head) {
    if (head.next == null) return head;
    let last = reverse(head.next);// 链表新头结点（原链尾）
    head.next.next = head;
    head.next = null;
    return last;
}

reverse函数定义理解：输入一个节点head，将「以head为起点」的链表反转，并返回反转之后的头结点。
所以执行完reverse(head.next)后，链表变为这个样子：

下面开始改变结点之间的链接

同样head.next=null不仅是为了断链，且是因为指向null代表结点为链尾
（因为反转的是整个链表，所以原表头肯定是新链表的链尾了）

然后我们再根据此法进阶，解出指定区间反转链表
对于函数reverseBetween(head, m, n)我们找到递归出口，m=1时即，反转链表的前n个
现在我们来解反转链表前n个：

解决思路和反转整个链表差不多，不过1作为head最后指向的不是null，而是链表的n结点的下一个元素

let tail_next = null;// 反转区域的链表尾的下一个对接结点
function reverseN(head, n) {
  if (n === 1) {
    tail_next = head.next;
    return head;
  }
  // 链表新头结点
  let last = reverseN(head.next, n - 1);
  head.next.next = head;
  head.next = tail_next; // 对比反转整个链表时 此处为null,反转区间时应该继续接入到链表里去
  return last;
}

而实现m-n之间的完整代码

function reverseBetween(head, m, n) {
    let tail_next = null;// 反转区域的链表尾的下一个对接结点
    if (m == 1) {
        return reverseN(head, n);
    }
    // 前进到反转的起点触发 base case
    head.next = reverseBetween(head.next, m - 1, n - 1);// n在前n个里使用的计数
    return head;
    function reverseN(head, n) {
        if (n === 1) {
            tail_next = head.next;
            return head;
        }
        // 链表新头结点
        let last = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = tail_next; // 对比反转整个链表时 此处为null,反转区间时应该继续接入到链表里去
        return last;
    }
}

🤔数据结构与算法

反转链表-指定区间

迭代-移动结点式反转

递归-从函数定义上理解

最后

参考

引申