138.随机链表的复制

链接：138.随机链表的复制
难度：Medium
标签：哈希表、链表
简介：给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。返回复制链表的头节点。

题解 1 - typescript

• 编辑时间：2021-07-22
• 执行用时：104ms
• 内存消耗：39.7MB
• 编程语言：typescript
• 解法介绍：节点复制。

function copyRandomList(head: Node | null): Node | null {
  if (head === null) return null;
  let p: Node | null = head;
  while (p) {
    const next = p.next;
    const newNode = new Node(p.val, next);
    p.next = newNode;
    p = next;
  }
  p = head;
  while (p) {
    const newNode = p.next;
    newNode!.random = p.random?.next ?? null;
    p = p.next!.next;
  }
  p = head;
  const ans = head.next;
  while (p) {
    const next = p.next?.next ?? null;
    const newNode = p.next!;
    newNode.next = next?.next ?? null;
    p.next = next;
    p = next;
  }
  return ans;
}

题解 2 - typescript

• 编辑时间：2021-03-14
• 执行用时：96ms
• 内存消耗：39.5MB
• 编程语言：typescript
• 解法介绍：先克隆一份再进行拆除。

function copyRandomList(head: Node | null): Node | null {
  if (head === null) return null;
  let p: Node | null = head;
  while (p !== null) {
    p.next = new Node(p.val, p.next, p.random);
    p = p.next.next;
  }
  p = head.next;
  while (p) {
    if (p.random) p.random = p.random!.next;
    p = p.next?.next ?? null;
  }
  const newHead: Node | null = head.next;
  p = head;
  while (p) {
    const q: Node = p.next!;
    p.next = q.next;
    q.next = q.next?.next ?? null;
    p = p.next;
  }
  return newHead;
}