链表

链表是线性数据结构（数据元素之间存在着“一对一”关系），链表中的每个元素是一个包含数据 data 和引用字段的对象，引用字段只有 next 为单向链表，同时有 prev 和 next 为双向链表。

链表基本操作

链表读取第 i 个节点或查找指定值的节点，均需要从头遍历，时间复杂度为 O(n)。

在不考虑查找节点的过程的情况下，更新（替换 data），插入（新节点 next 指针指向插入位置节点，前一节点的 next 指针指向新节点）、删除（前一节点 next 指针指向下一节点，当前节点置空），时间复杂度均为 O(1)。

设计链表

设计单向链表的实现。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。假设链表中的所有节点都是 0 ~ size - 1 的。

linkList.ts

import LinkNode from './linkNode';

export default class MyLinkedList<T> {
  size: number; // 链表长度

  head: LinkNode<T> | null; // 头结点

  constructor() {
    this.size = 0;
    this.head = null;
  }

  /**
   * 获取链表中 index 位置的节点。如果索引无效，则返回 null。
   * @param index
   */
  getNode(index: number): LinkNode<T> | null {
    if (index < 0 || index >= this.size) {
      return null;
    }
    // index 有效，所以 node.next 和 node.val 是存在的。
    let node = this.head as LinkNode<T>;
    for (let i = 0; i < index; i += 1) {
      node = node.next as LinkNode<T>;
    }
    return node;
  }

  /**
   * 获取链表中 index 位置的节点值。如果索引无效，则返回-1。
   * @param index
   */
  get(index: number): T | -1 {
    const node = this.getNode(index);
    return node?.val ?? -1;
  }

  /**
   * 在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
   * @param val
   */
  addAtHead(val: T): void {
    const newHead = new LinkNode(val);
    newHead.next = this.head;
    this.head = newHead;
    this.size += 1;
  }

  /**
   * 将值为 val 的节点追加到链表的最后一个元素。
   * @param val
   */
  addAtTail(val: T): void {
    const oldTailNode = this.getNode(this.size - 1);
    const newTailNode = new LinkNode(val);
    this.size += 1;
    if (oldTailNode === null) {
      this.head = new LinkNode(val);
      return;
    }
    oldTailNode.next = newTailNode;
  }

  /**
   * 在链表中的 index 位置之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果 index 小于0，则在头部插入节点。
   * @param index
   * @param val
   */
  addAtIndex(index: number, val: T): void {
    if (index > this.size) return;
    // 尾插
    if (index === this.size) {
      this.addAtTail(val);
      return;
    }
    // 头插
    if (index < 0) {
      this.addAtHead(val);
      return;
    }
    const prevNode = this.getNode(index - 1) as LinkNode<T>;
    const node = new LinkNode(val);
    node.next = prevNode.next;
    prevNode.next = node;
    this.size += 1;
  }

  /**
   * 如果索引 index 有效，则删除链表中的第 index 个节点。
   * @param index
   */
  deleteAtIndex(index: number): void {
    // index 无效
    if (index < 0 || index >= this.size || this.size === 0) return;
    this.size -= 1;
    // 删除头节点
    if (index === 0) {
      this.head = this.head?.next as LinkNode<T> | null;
      return;
    }
    const prevNode = this.getNode(index - 1) as LinkNode<T>;
    const deleteNode = prevNode.next as LinkNode<T>;
    prevNode.next = deleteNode.next;
  }
}

linkNode.ts

// 节点
export default class LinkNode<T> {
  val: T;

  next: LinkNode<T> | null;

  constructor(val: T, next?: LinkNode<T> | null) {
    this.val = val;
    this.next = next ?? null;
  }
}

算法题

1. 从尾到头打印链表

题目描述：输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

分析：

遍历 + 反转，从尾到头将链表节点值打印成数组 array，比如 1 -> 2 -> 3 -> 4 -> 5 -> null 打印为 [5, 4, 3, 2, 1]，遍历节点并将节点值依次放入数组中，直到遍历完成，最后反转数组即可。也可以利用栈后进先出的特点，将节点从头到尾一次入栈，然后再依次出栈即可。

求解：

reversePrint.ts

import LinkNode from '../设计链表/linkNode';

// 遍历 + 反转法
function reversePrint1<T extends number>(head: LinkNode<T> | null): number[] {
  let node = head;
  const res: number[] = [];
  while (node !== null) {
    res.push(node.val);
    node = node.next;
  }
  return res.reverse();
}

// 栈
function reversePrint2<T extends number>(head: LinkNode<T> | null): number[] {
  let node = head;
  // 栈
  const stack: LinkNode<T>[] = [];
  const res: number[] = [];
  while (node !== null) {
    stack.push(node);
    node = node.next;
  }
  const size = stack.length;
  for (let i = 0; i < size; i += 1) {
    res.push(stack.pop()?.val as number);
  }
  return res;
}

linkNode.ts

// 节点
export default class LinkNode<T> {
  val: T;

  next: LinkNode<T> | null;

  constructor(val: T, next?: LinkNode<T> | null) {
    this.val = val;
    this.next = next ?? null;
  }
}

2. 链表倒数第 k 个节点

题目描述：输入一个链表，输出该链表中倒数第 k 个节点。为了符合大多数人的习惯，本题从 1 开始计数，即链表的尾节点是倒数第 1 个节点。 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

分析：

两次循环法，倒数第 k 个节点，即顺数第 length - k + 1 个节点，由于是单链表，没有链表长度信息，因此第一步遍历链表，计算出链表长度。第二步，遍历链表到第 length - k + 1 个节点（index = length - k），需要遍历 n + n - k + 1 步。

快慢指针法，快指针先走 k 步，然后快慢指针以相同的速度移动，直到快指针到 null，只需要遍历 n 步（因为快指针走了 n 步）。

求解：

getKthFromEnd.ts

import LinkNode from '../设计链表/linkNode';

// 两次遍历
function getKthFromEnd<T extends number>(head: LinkNode<T> | null, k: number): LinkNode<T> | null {
  let node = head;
  // 计算链表长度
  let size = 0;
  while (node !== null) {
    node = node.next;
    size += 1;
  }
  // 倒数第 k 个 节点，对应于正数第 size - k + 1 个节点，即 index = size - k
  const index = size - k;
  if (index < 0) return null;
  node = head;
  for (let i = 1; i <= index; i += 1) {
    node = node?.next as LinkNode<T>;
  }
  return node;
}

// 快慢指针
function getKthFromEnd2<T extends number>(head: LinkNode<T> | null, k: number): LinkNode<T> | null {
  let fast = head;
  let slow = head;
  let i = 0;
  while (i < k) {
    if (fast === null) {
      // 超出链表长度
      return null;
    }
    fast = fast.next;
    i += 1;
  }
  while (fast !== null) {
    // 快指针走到 null 的时候，慢指针即为倒数第 k 个 节点
    slow = slow?.next as LinkNode<T>;
    fast = fast.next;
  }
  return slow;
}

linkNode.ts

// 节点
export default class LinkNode<T> {
  val: T;

  next: LinkNode<T> | null;

  constructor(val: T, next?: LinkNode<T> | null) {
    this.val = val;
    this.next = next ?? null;
  }
}

3. 反转链表

题目描述： 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

分析：

原地反转，定义前驱节点，当前节点，遍历链表，然后缓存后驱节点，将当前节点链接到前驱节 3 点，然后先更新前驱节点为当前节点，再更新当前节点为后驱节点，直到遍历结束返回前驱节点即可。

递归，假设链表的其余部分已经被反转，现在是要反转前面的部分，则需要将当前节点的下一节点的next指针指向当前节点，然后将当前节点的next 置为null;

求解：

reverseList.ts

import LinkNode from '../设计链表/linkNode';

// 原地反转
function reverseList1<T extends number>(head: LinkNode<T> | null): LinkNode<T> | null {
  // 当前节点
  let currentNode = head;
  // 上一节点
  let prevNode: LinkNode<T> | null = null;
  while (currentNode !== null) {
    // 首先缓存下一节点
    const nextNode = currentNode.next;
    // 当前节点指向上一节点
    currentNode.next = prevNode;

    // 更新当前节点和上一节点, 直到当前节点变成 null， 上一节点即为尾节点
    prevNode = currentNode;
    currentNode = nextNode;
  }
  return prevNode;
}

// 递归
function reverseList2<T extends number>(head: LinkNode<T> | null): LinkNode<T> | null {
  if (head == null || head.next == null) {
    return head;
  }
  const newHead = reverseList2(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

linkNode.ts

// 节点
export default class LinkNode<T> {
  val: T;

  next: LinkNode<T> | null;

  constructor(val: T, next?: LinkNode<T> | null) {
    this.val = val;
    this.next = next ?? null;
  }
}

4. 合并两个排序链表

题目描述：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

分析：

递归法，对比节点值的大小，小的作为头节点，下一个节点是除去小的节点的链表和另一链表的合并，边界条件是其中一个链表为空，则直接返回另一个链表即可。

迭代法，首先，若其中一个链表为空，则直接返回另一个链表即可，否则初始化一个虚假的头结点，当前节点初始化为虚假节点，不断对比节点值大小，将小节点连接在新链表后面，然后更新新链表的尾节点。直到其中一个链表遍历结束，将另一个链表直接链接在末尾。

求解：

mergeTwoLists.ts

import LinkNode from '../设计链表/linkNode';

// 递归
function mergeTwoLists<T extends number>(l1: LinkNode<T> | null, l2: LinkNode<T> | null): LinkNode<T> | null {
  // 其中一个链表为空，则返回另一个即可
  if (l1 === null || l2 === null) {
    return l1 || l2;
  }
  // 合并后的链表头结点
  let l: LinkNode<T> | null = null;
  if (l1.val <= l2.val) {
    l = l1;
    l.next = mergeTwoLists(l1.next, l2);
  } else {
    l = l2;
    l.next = mergeTwoLists(l1, l2.next);
  }
  return l;
}

// 双指针遍历
function mergeTwoLists1<T extends number>(l1: LinkNode<T> | null, l2: LinkNode<T> | null): LinkNode<number> | null {
  // 其中一个链表为空，则返回另一个即可
  if (l1 === null || l2 === null) {
    return l1 || l2;
  }
  // 新链表的虚拟头结点
  const preHead = new LinkNode(-1);
  let prev = preHead;
  while (l1 !== null && l2 !== null) {
    // 遍历到其中一个末尾
    if (l1.val <= l2.val) {
      prev.next = l1;
      l1 = l1.next;
    } else {
      prev.next = l2;
      l2 = l2.next;
    }
    prev = prev.next;
  }
  // 将另一链表直接添加到末尾
  prev.next = l1 === null ? l2 : l1;

  return preHead.next;
}

linkNode.ts

// 节点
export default class LinkNode<T> {
  val: T;

  next: LinkNode<T> | null;

  constructor(val: T, next?: LinkNode<T> | null) {
    this.val = val;
    this.next = next ?? null;
  }
}

5. 复杂链表的复制

题目描述：请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。

分析：

三次遍历+拆分，首先对复杂链表进行遍历，在每个节点后面复制一个与当前节点相同的节点（先不理会 random 指针），即 1 -> 2 -> 3 -> 4 -> 5 -> null 变成 1 -> 1 -> 2 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 -> 5 -> null；然后是再遍历一次原链表（即遍历步长为 2），将 random 指针进行复制；最后再遍历一次，将原链表的节点指向原来的下一个节点，复制链表的节点指向下一个复制的节点，分离成原链表和复制链表，注意判断最后一个复制节点是否为 null。

两次遍历+哈希，可以在初次遍历的时候用哈希保存原节点到复制节点（只复制值）的映射，二次遍历时更新复制节点的 next 和 random 指针为与原节点 next 和 random 指针对应的复制节点即可。

求解：

copyRandomList.ts

import RandomLinkNode from '../设计链表/randomLinkNode';

// 三次遍历 + 拆分
function copyRandomList(head: RandomLinkNode | null) {
  // 复制每个节点插入到节点后面
  let node = head;
  while (node !== null) {
    const copyNode = new RandomLinkNode(node.val, node.next);
    node.next = copyNode;
    node = copyNode.next;
  }
  // 复制 random 指针
  node = head;
  while (node !== null && node.next !== null) {
    if (node.random !== null) {
      // 复制节点的 random 指针应该指向原节点的 random 指针指向的节点的下一节点
      node.next.random = node.random.next;
    }
    node = node.next.next;
  }
  // 将两个链表断开
  // 复制链表头结点
  const copyHead = head?.next;
  // 恢复原始链表
  node = head;
  while (node !== null && node.next !== null) {
    const copyNode = node.next;
    node.next = node.next.next;
    copyNode.next = copyNode.next?.next ?? null;
    node = node.next;
  }
  return copyHead;
}

// 哈希 + 两次遍历
function copyRandomList2(head: RandomLinkNode | null) {
  const map = new Map<RandomLinkNode, RandomLinkNode>();
  let node = head;
  while (node !== null) {
    map.set(node, new RandomLinkNode(node.val));
    node = node.next;
  }
  node = head;
  while (node !== null) {
    const copyNode = map.get(node) as RandomLinkNode;
    copyNode.next = node.next ? (map.get(node.next) as RandomLinkNode) : null;
    copyNode.random = node.random ? (map.get(node.random) as RandomLinkNode) : null;
    node = node.next;
  }
  return head !== null ? map.get(head) : null;
}

randomLinkNode.ts

export default class RandomLinkNode {
  val: number;

  next: RandomLinkNode | null;

  random: RandomLinkNode | null;

  constructor(val: number, next?: RandomLinkNode | null, random?: RandomLinkNode | null) {
    this.val = val;
    this.next = next ?? null;
    this.random = random ?? null;
  }
}

6. 删除链表中的重复节点

题目描述：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，分为重复结点保留（链表 1->2->3->3->4->4->5 处理后为 1->2->3->4->5）和重复的结点不保留（链表 1->2->3->3->4->4->5 处理后为 1->2->5）两种情况，返回链表头指针。

分析：

对于重复节点保留的情况，从头节点开始遍历，判断当前节点下一个节点是否等于当前节点，如果相等，则当前节点的下一节点为下下节点，直到不等于或者当前节点下一节点为空。

对于重复节点不保留的情况，考虑到头节点可能重复，在链表前添加一个虚节点，从该节点开始遍历，当 next 节点和 next.next 节点不为空时，若 next 节点和 next.next 节点的值相等，记录该值，不断将当前节点的 next 指向为 next.next节点，直到 next 节点值不等于该值或 next 为空。

求解：

copyRandomList.ts

import LinkNode from '../设计链表/linkNode';

// 保留重复节点
function deleteDuplicates1(head: LinkNode<number> | null): LinkNode<number> | null {
  let node = head;
  while (node !== null) {
    while (node.next !== null && node.val === node.next.val) {
      node.next = node.next.next;
    }
    node = node.next;
  }
  return head;
}

// 不保留重复节点
function deleteDuplicates2(head: LinkNode<number> | null): LinkNode<number> | null {
  // 虚头节点
  const dummy = new LinkNode(-1, head);
  let node = dummy;
  while (node.next !== null && node.next.next !== null) {
    if (node.next.val === node.next.next.val) {
      const { val } = node.next;
      while (node.next !== null && node.next.val === val) {
        node.next = node.next.next;
      }
    } else {
      node = node.next;
    }
  }
  return dummy.next;
}

linkNode.ts

// 节点
export default class LinkNode<T> {
  val: T;

  next: LinkNode<T> | null;

  constructor(val: T, next?: LinkNode<T> | null) {
    this.val = val;
    this.next = next ?? null;
  }
}

7. 两个链表的第一个公共节点

题目描述：输入两个链表，找出它们的第一个公共结点。

分析：

遍历法，两个链表的公共节点是指从公共节点开始的所有节点是两个链表的共有部分（节点的存储地址相同，因此判断节点对象是否相等）。既然公共节点及其之后的节点完全相同，即不同的是公共节点之前的部分，也就可能存在一个长度差 diff，通过遍历两个链表的长度可以求出 diff，让长的链表先遍历 diff 个节点，以此开始的两个链表的长度相同，那么当遍历到相同节点即第一个公共节点。

求解：

findFirstCommonNode.ts

import LinkNode from '../设计链表/linkNode';

// 长短diff遍历法
function getIntersectionNode(headA: LinkNode<number> | null, headB: LinkNode<number> | null): LinkNode<number> | null {
  // 求链表长度
  function getSize<T>(head: LinkNode<T> | null): number {
    let node: LinkNode<T> | null = head;
    let size = 0;
    while (node !== null) {
      node = node.next;
      size += 1;
    }
    return size;
  }
  const lenA = getSize(headA);
  const lenB = getSize(headB);
  // 短链表和长链表
  let short = lenA > lenB ? headB : headA;
  let long = lenA > lenB ? headA : headB;
  const diff = Math.abs(lenA - lenB);
  // 长链表先走 diff 步
  for (let i = 0; i < diff && long !== null; i += 1) {
    long = long.next;
  }
  while (short !== null && long !== null && short !== long) {
    short = short.next;
    long = long.next;
  }
  return short;
}

linkNode.ts

// 节点
export default class LinkNode<T> {
  val: T;

  next: LinkNode<T> | null;

  constructor(val: T, next?: LinkNode<T> | null) {
    this.val = val;
    this.next = next ?? null;
  }
}

8. 链表中环的入口节点

题目描述：给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。说明：不允许修改给定的链表。

分析：

哈希法，遍历链表，将节点不存在 map 中，放入 map 中，若已存在说明是环的入口节点，返回该节点，若遍历到链表末尾 null 若还无环，返回 null。

快慢指针法，遍历链表，快指针走两步，慢指针每次走一步，快慢指针必定在环内相遇，此时快指针走过 a + n(b + c) + b = a + (n+1)b + nc， 而慢指针走过的路程 a + b (因为一定还没走完环的第一圈)，两者满足 a + (n+1)b + nc = 2(a + b)， 所以 a = c + (n − 1)(b + c)，即链表头结点到环入口节点的距离 = 相遇点到环入口距离 + （n - 1）* 环，只需要让两新指针分别从头结点和相遇节点单步出发，直到相遇即可。

求解：

detectCycle.ts

import LinkNode from '../设计链表/linkNode';

// 哈希法
function detectCycle1(head: LinkNode<number> | null): LinkNode<number> | null {
  const map = new Map<LinkNode<number>, number>();
  let node = head;
  while (node !== null) {
    if (map.has(node)) {
      return node;
    }
    map.set(node, 1);
    node = node.next;
  }
  return null;
}

// 快慢指针法
function detectCycle2(head: LinkNode<number> | null): LinkNode<number> | null {
  let slow = head;
  let fast = head;
  while (slow !== null && fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      // 相遇
      let nodeA = head;
      let nodeB = slow;
      while (nodeA !== null && nodeB !== null && nodeA !== nodeB) {
        // 两新指针再次相遇
        nodeA = nodeA.next;
        nodeB = nodeB.next;
      }
      return nodeA;
    }
  }
  return null;
}

linkNode.ts

// 节点
export default class LinkNode<T> {
  val: T;

  next: LinkNode<T> | null;

  constructor(val: T, next?: LinkNode<T> | null) {
    this.val = val;
    this.next = next ?? null;
  }
}