问题

剑指 Offer 35. 复杂链表的复制
难度中等57
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：
剑指offer35. 复杂链表的复制（双百） - 图1
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：
剑指offer35. 复杂链表的复制（双百） - 图2
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：
剑指offer35. 复杂链表的复制（双百） - 图3
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

示例 4：
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。


提示：

  • -10000 <= Node.val <= 10000
  • Node.random 为空（null）或指向链表中的节点。

  • 节点数目不超过 1000 。

    解答：

    利用一个 map 将旧节点与新节点做映射，key 是旧节点，value 是新节点。
    首先遍历整个待复制的链表，并添加到 map 中，第二次遍历的时候，复制链表的 random 指向：
    map.get(oldNode).ramdon = map.get(oldNode) ，map.get(oldNode) 获取到的是新节点， map.get(oldNode.ramdon) 获取到的是，新节点 random 的指向。

    1. /*
    2. // Definition for a Node.
    3. class Node {
    4.   int val;
    5.   Node next;
    6.   Node random;
    8.   public Node(int val) {
    9.       this.val = val;
    10.       this.next = null;
    11.       this.random = null;
    12.   }
    13. }
    14. */
    15. class Solution {
    16.   public Node copyRandomList(Node head) {
    17.       if(head == null) return head;
    18.       // key: 旧节点，value：新复制的节点
    19.       Map<Node, Node> old2new = new HashMap<>();
    20.       Node res = new Node(-1);
    21.       Node pre = res;
    22.       Node nextCopy = head;
    23.       // 复制旧节点，并将旧节点与新节点做映射
    24.       while( (nextCopy) != null){
    25.           Node node = new Node(nextCopy.val);
    26.           old2new.put(nextCopy, node);
    27.           pre.next = node;
    28.           pre = node;
    29.           nextCopy = nextCopy.next;
    30.       }
    31.       // 复制 random 的指向
    32.       Node ranCopy = head;
    33.       while(ranCopy != null){
    34.           if(ranCopy.random == null)
    35.               old2new.get(ranCopy).random = null;
    36.           else 
    37.               old2new.get(ranCopy).random = old2new.get(ranCopy.random);
    38.           ranCopy = ranCopy.next;
    39.       }
    40.       return res.next;
    41.   }
    42. }

    执行结果：AC

显示详情
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：39.8 MB, 在所有 Java 提交中击败了100.00%的用户