快慢指针和多指针

快慢指针 - 删除链表的倒数第 N 个节点

给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

function removeNthFromEnd(head, n) {
  // 找到链表的倒数第n+1个节点
  const newHead = new ListNode(-1);
  newHead.next = head;
  let fast = (slow = newHead);
  while (k) {
    fast = fast.next;
    k--;
  }
  while (fast.next) {
    slow = slow.next;
    fast = fast.next;
  }
  slow.next = slow.next.next;
  return newHead.next;
}

多指针法 — 链表的反转

定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

// 递归
function reverseList(head) {
  if (!head || !head.next) return head;
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

// 迭代

function reverseList(head) {
  if (head === null || !head.next) return head;
  let cur = head,
    prev = null;
  while (cur) {
    const next = cur.next;
    cur.next = prev;
    // next.next = cur;
    prev = cur;
    cur = next;
  }
  return prev;
}

局部反转一个链表

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

// 入参是头结点、m、n
function reverseBetween(head, m, n) {
  // 定义pre、cur，用leftHead来承接整个区间的前驱结点
  let pre, cur, leftHead;
  // 别忘了用 dummy 嗷
  const dummy = new ListNode();
  // dummy后继结点是头结点
  dummy.next = head;
  // p是一个游标，用于遍历，最初指向 dummy
  let p = dummy;
  // p往前走 m-1 步，走到整个区间的前驱结点处
  for (let i = 0; i < m - 1; i++) {
    p = p.next;
  }
  // 缓存这个前驱结点到 leftHead 里
  leftHead = p;
  // start 是反转区间的第一个结点
  let start = leftHead.next;
  // pre 指向start
  pre = start;
  // cur 指向 start 的下一个结点
  cur = pre.next;
  // 开始重复反转动作
  for (let i = m; i < n; i++) {
    let next = cur.next;
    cur.next = pre;
    pre = cur;
    cur = next;
  }
  //  leftHead 的后继结点此时为反转后的区间的第一个结点
  leftHead.next = pre;
  // 将区间内反转后的最后一个结点 next 指向 cur
  start.next = cur;
  // dummy.next 永远指向链表头结点
  return dummy.next;
}