本文共 1978 字，大约阅读时间需要 6 分钟。

为了实现这个问题，我们需要构造一个链表的深拷贝，包括每个节点的值、next指针和random指针。深拷贝必须由新的节点组成，每个节点的值与原节点一致，并且指针也应指向复制链表中的节点。

方法思路

为了解决这个问题，我们使用分阶段迭代的方法来构造深拷贝。具体步骤如下：

这种方法的时间复杂度为O(n)，因为只遍历了链表两次。空间复杂度为O(n)，由于我们需要存储旧节点到新节点的映射。

解决代码

class Solution {    public Node copyRandomList(Node head) {        if (head == null) return null;        // 使用字典记录旧节点到新节点的映射        Map
   
     map = new HashMap<>();        // 处理头节点        Node newHead = new Node(head.val);        map.put(head, newHead);        // 迭代处理链表中的每个节点（处理next指针）        Node current = newHead;        while (head != null) {            // 处理当前节点的下一个节点            Node nextHead = head.next;            Node newNode = new Node(head.val);            map.put(head, newNode);            if (current.next != null) {                // 设置复制节点的下一个节点                newNode.next = current.next;                // 需要保持原节点和新节点的next指针对应                // current的下一个节点可能已经处理过了                current.next = newNode;            } else {                // 处理null的情况                current.next = newNode;            }            current = newNode;            head = nextHead != null ? nextHead : null;        }        // 处理每个节点的random指针        current = newHead;        while (current != null) {            Node randomTarget = current.random; // 获取当前节点的random指针目标节点            // 解决random可能为null的情况            if (randomTarget != null) {                // 需要将其映射到复制链表中的对应节点                current.random = map.get(randomTarget); // map已经有了所有oldNode <-> newNode的映射            }            // 处理下一个节点            current = current.next;        }        return newHead;    }}
   

代码解释

这种方法通过分阶段处理，确保每个节点及其指针都被正确拷贝，从而完成深拷贝任务。

转载地址：http://fcwaz.baihongyu.com/