1. 题目描述

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Example 1:

Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

Note:

You must return the copy of the given head as a reference to the cloned list.

2. 解题

这道题可以用一些“笨办法”来解,即想办法记住原节点和复制后的节点的对应关系,这样在找random节点的时候,直接用对应关系找到新链表中对应的random,然后直接让指针指过去就好了。为了优化时间复杂度可以用哈希表存储这种对应关系,这也可以得到O(N)的时间复杂度。

但这篇博客要介绍的是另一种非常神奇的方法,其本质也是记住对应关系,但这种方法真的很难想到。

首先下图是原链表:

第一步是在每个原链表节点后面增加一个拷贝,先只拷贝next指针:

第二步,根据每一个原节点的random指针来赋值新节点的random指针,即让新节点的random指向原节点的 random->next:

第三步,分离出新链表。

3. 代码

class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}
};

Node* getNewNode(int val) {
    Node* newNode = (Node *)malloc(sizeof(Node));
    newNode->val = val;
    newNode->next = NULL;
    newNode->random = NULL;

    return newNode;
}

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == NULL) {
            return NULL;
        }

        // 1. 遍历链表,往每个节点后面插入一个复制节点
        Node* curr = head;
        Node* newNode = NULL;

        while (curr) {
            newNode = getNewNode(curr->val);
            newNode->next = curr->next;
            curr->next = newNode;
            curr = newNode->next;
        }

        // 2. 复制random指针
        curr = head;
        while (curr) {
            curr->next->random = curr->random ? curr->random->next : NULL;
            curr = curr->next->next;
        }

        // 3. 分离出新链表
        Node* res = head->next;
        Node* p1 = head;
        Node* p2 = head->next;

        while (p2) {
            p1->next = p2->next;
            p1 = p2;
            p2 = p2->next;
        }

        return res;
    }
};
Last modification:September 8th, 2019 at 08:19 pm