来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/copy-list-with-random-pointer

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

一、题目描述

给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个[val, random_index]表示:

  • val:一个表示 Node.val 的整数。
  • random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。

示例 1:

  • 输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
  • 输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2:

  • 输入:head = [[1,1],[2,1]]
  • 输出:[[1,1],[2,1]]

提示:

  • -10000 <= Node.val <= 10000。
  • Node.random 为空(null)或指向链表中的节点。
  • 节点数目不超过 1000 。

二、题目解析

《剑指offer》原题,详细解析《剑指offer》面试题35:复杂链表的复制

三、代码

class Solution {
private:
    /*
     * 克隆所有的节点,并串到原始节点中去
     * @head 链表的头结点
     */
    void clone_all_nodes(Node *head) {
        Node *node, *clone;
        node = head;
        while (node) {
            // 拷贝节点
            clone = new Node(node->val);
            clone->next = node->next;
            clone->random = node->random;
            // 修改p节点的下一个节点指向新创建的节点
            node->next = clone;
            // 移动p指针到下一个节点
            node = clone->next;
        }
    }

    /*
     * 修正所有克隆节点的随机指针的地址
     * @head 链表的头结点
     */
    void fix_random_nodes(Node *head) {
        // node/q节点分别表示原始节点和被克隆的节点
        Node *node, *clone;
        node = head;
        while (node) {
            clone = node->next;
            // 修正q节点的random指针,注意random可能为null
            if (clone->random)
                clone->random = clone->random->next;
            node = clone->next;
        }
    }

    Node *reconnect_nodes(Node *head) {
        Node *node, *clone;
        Node *new_head = head->next;

        node = head;
        while (node) {
            clone = node->next;
            // 备份下一个节点的指针
            node->next = clone->next;
            // 连接到新克隆的节点,注意next可能为null
            if (clone->next) {
                clone->next = clone->next->next;
            }
            node = node->next;
        }
        return new_head;
    }

public:
    Node *copyRandomList(Node *head) {
        Node *new_head;
        if (head == nullptr) {
            return nullptr;
        }
        clone_all_nodes(head);
        fix_random_nodes(head);
        new_head = reconnect_nodes(head);
        return new_head;
    }
};

最后修改:2020 年 02 月 09 日
喜欢就给我点赞吧