92.反转链表II

链接：92.反转链表II
难度：Medium
标签：链表
简介：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

题解 1 - typescript

• 编辑时间：2021-03-06
• 执行用时：80ms
• 内存消耗：39.5MB
• 编程语言：typescript
• 解法介绍：递归计算剩余翻转节点个数。

function reverseList(head: ListNode, count: number): ListNode | null {
  if (count === 1 || head.next === null) return head;
  const tail = head.next;
  const nextList = reverseList(tail, count - 1);
  head.next = tail.next;
  tail.next = head;
  return nextList;
}
function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
  const dummyHead = new ListNode(0, head);
  let temp: ListNode = dummyHead;
  const count = right - left + 1;
  while (--left) temp = temp.next!;
  temp!.next = reverseList(temp.next!, count);
  return dummyHead.next;
}

题解 2 - typescript

• 编辑时间：2021-03-18
• 执行用时：100ms
• 内存消耗：39.5MB
• 编程语言：typescript
• 解法介绍：递归翻转。

function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
  if (head === null) return null;
  const dummyNode = new ListNode(0, head);
  let p: ListNode | null = dummyNode;
  let c = 0;
  let prev!: ListNode;
  while (c !== left && p !== null) {
    cpp;
    prev = p;
    p = p.next;
  }
  const reverse = (node: ListNode | null, count: number): ListNode | null => {
    if (count === 1 || node === null) return node;
    const nextNode: ListNode = node.next!;
    const newNode = reverse(nextNode, count - 1);
    node.next = nextNode.next;
    nextNode.next = node;
    return newNode;
  };
  const newNode = reverse(p, right - left + 1);
  prev.next = newNode;
  return dummyNode.next;
}