反转链表2

题目描述：给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]

方法一：头插法

在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。

第 1 步完成以后「拉直」的效果如下：

第 2 步，同理。同样需要注意 「穿针引线」操作的先后顺序。

第 2 步完成以后「拉直」的效果如下：

第 3 步，同理。

第 3 步完成以后「拉直」的效果如下：

/**
   * Definition for singly-linked list.
   * public class ListNode {
   *     int val;
   *     ListNode next;
   *     ListNode() {}
   *     ListNode(int val) { this.val = val; }
   *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   * }
   */
class Solution {
  public ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummyHead = new ListNode(0);
    dummyHead.next = head;
    ListNode pre = dummyHead;
    for(int i = 0; i < left - 1; i++) {
      pre = pre.next;
    }

    ListNode cur = pre.next;
    for(int i = 0; i < right - left; i++) {
      ListNode next = cur.next;
      cur.next = next.next;
      next.next = pre.next;
      pre.next = next;
    }
    return dummyHead.next;
  }
}

var reverseBetween = function(head, left, right) {
  const dummyHead = new ListNode(-1);
  dummyHead.next = head;
  let pre = dummyHead;
  for (let i = 0; i < left - 1; i++) {
    pre = pre.next;
  }

  let cur = pre.next;
  for (let i = 0; i < right - left; i++) {
    const next = cur.next;
    cur.next = next.next;
    next.next = pre.next;
    pre.next = next;
  }
  return dummyHead.next;
};

复杂度分析：

• 时间复杂度：O(N)，其中 N 是链表总节点数。最多只遍历了链表一次，就完成了反转。

• 空间复杂度：O(1)。只使用到常数个变量。

执行结果：通过

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

• 内存消耗：36.2 MB, 在所有 Java 提交中击败了12.34%的用户

方法二：递归

先定位到要开始反转的节点， 其中head往后移, m和n就要变小

当 m 等于 1 时，此时 head 就是要反转的第一个节点，调用反转链表前 n个节点的函数进行反转

• 解决思路和反转整个链表差不多，具体的区别：
  • base case 变为 n == 1，反转一个元素，就是它本身，同时要记录后驱节点。
  • 反转链表中我们把 head.next 设置为 null，因为整个链表反转后原来的 head 变成了整个链表的最后一个节点。但现在 head 节点在递归反转之后不一定是最后一个节点了，所以要记录后驱 successor（第 n + 1 个节点），反转之后将 head 连接上。

class Solution {
  public ListNode reverseBetween(ListNode head, int m, int n) {
    // 相当于反转链表的前 n 个节点
    if (m == 1) {
      return reverseTopN(head, n);
    }

    // 前进到反转的起点触发 基础条件
    head.next = reverseBetween(head.next, m-1, n-1);
    return head;
  }

  ListNode successor = null; // 后驱节点

  // 将链表的前 n 个节点反转（n <= 链表长度）
  private ListNode reverseTopN(ListNode head, int n) {
    if (n == 1) {
      // 记录第 n + 1 个节点
      successor = head.next;
      return head;
    }

    // 以 head.next 为起点，需要反转前 n - 1 个节点
    ListNode newHead = reverseTopN(head.next, n-1);
    head.next.next = head;
    // 让反转之后的 head 节点和后面的节点连起来
    head.next = successor;
    //每层递归函数都返回反转的新链表头
    return newHead;
  }
}

let successor;
var reverseBetween = function (head, left, right) {
  // 反转以 head 为起点的 n 个节点，返回新的头结点
  let reverseN = (head, n) => {
    if (n == 1) {
      // 记录第 n + 1 个节点
      successor = head.next;
      return head;
    }
    // 以 head.next 为起点，需要反转前 n - 1 个节点
    let newHead = reverseN(head.next, n - 1);
    head.next.next = head;
    // 让反转之后的 head 节点和后面的节点连起来
    head.next = successor;
    return newHead;
  };

  if (left == 1) {
    // 相当于反转前 n 个元素
    return reverseN(head, right);
  }

  // 前进到反转的起点触发 base case
  head.next = reverseBetween(head.next, left - 1, right - 1);

  return head;
};

复杂度分析

• 时间复杂度：O(n)

• 空间复杂度：O(n)

执行结果：通过

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

• 内存消耗：36 MB, 在所有 Java 提交中击败了62.16%的用户