2023-9-18

9-18

链表

题号138. 复制带随机指针的链表

题目 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

解题思路，使用哈希表实现方法二使用拼接实现

哈希表实现

/**
 * Definition for Node.
 * class Node {
 *     val: number
 *     next: Node | null
 *     random: Node | null
 *     constructor(val?: number, next?: Node, random?: Node) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *         this.random = (random===undefined ? null : random)
 *     }
 * }
 */


function copyRandomList(head: Node | null): Node | null {
  if (head === null) return null;
  let cur: Node | null = head;
  const map: Map<Node, Node> = new Map();

  // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
  while (cur !== null) {
    map.set(cur, new Node(cur.val));
    cur = cur.next;
  }

  cur = head;

  // 4. 构建新链表的 next 和 random 指向
  while (cur !== null) {
    if (cur.next) {
      map.get(cur)!.next = map.get(cur.next);
    }
    if (cur.random) {
      map.get(cur)!.random = map.get(cur.random);
    }
    cur = cur.next;
  }

  // 5. 返回新链表的头节点
  return map.get(head) || null;
}

链表拼接实现

/**
 * Definition for Node.
 * class Node {
 *     val: number
 *     next: Node | null
 *     random: Node | null
 *     constructor(val?: number, next?: Node, random?: Node) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *         this.random = (random===undefined ? null : random)
 *     }
 * }
 */

function copyRandomList(head: Node | null): Node | null {
    if(head===null)return null
    let cur:Node = head
    // 1. 复制各节点，并构建拼接链表
    while(cur!==null){
        let tmp:Node = new Node(cur.val)
        tmp.next = cur.next
        cur.next = tmp
        cur = tmp.next
    }
    // 2. 构建各新节点的 random 指向
    cur = head;
    while(cur != null) {
        if(cur.random != null)
            cur.next.random = cur.random.next;
        cur = cur.next.next;
    }
    // 3. 拆分两链表
    cur = head.next;
    let pre = head, res = head.next;
    while(cur.next != null) {
        pre.next = pre.next.next;
        cur.next = cur.next.next;
        pre = pre.next;
        cur = cur.next;
    }
    pre.next = null; // 单独处理原链表尾节点
    return res;      // 返回新链表头节点


};