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

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

1
2
3
4
5
6
7
8
/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        //建立结点与当前位置的映射
        std::map<RandomListNode *, int> node_map;
        //存放copy了的所有结点。按位置。
        std::vector<RandomListNode *> node_vec;
        RandomListNode *ptr = head;
        int i = 0;
        while(ptr){
            //创建与旧链表相等的结点。copy其中的值。
            node_vec.push_back(new RandomListNode(ptr->label));
            // 建立结点与当前位置的映射。
            node_map[ptr] = i;
            ptr = ptr->next;
            i++;
        }
        //push尾结点
        node_vec.push_back(0);
        ptr = head;
        i = 0;
        while(ptr){
            //将依次排列的结点的next相连接。
            node_vec[i]->next = node_vec[i+1];
            if(ptr->random){
                //找到该结点对应所指向的random所映射的位置。然后赋给当前结点。
                int id = node_map[ptr->random];
                node_vec[i]->random = node_vec[id];
            }
            ptr = ptr->next;
            i++;
        }
        //返回首结点
        return node_vec[0];
    }
};

思路:

如果没有random域，copy链表只要依次创建结点，并将当前结点的next指向下一个结点就完成了。

有random域会比较麻烦一些。需要通过建立一张结点与其位置的表来完成。

当需要填充random指向时，通过原链表的random域在表中的位置来将vector中这一位置的结点地址赋给random域。

Solution2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        //为每个节点添加一个副本，链接在当前节点之后。
        RandomListNode* cur = head;
        while(cur){
            RandomListNode* next = cur->next;
            cur->next = new RandomListNode(cur->label);
            cur->next->next = next;
            cur = cur->next->next;
        }
        //copy随机指针
        cur = head;
        while(cur){
            RandomListNode* random = cur->random;
            //如果随机指针不为空
            if(random) cur->next->random = random->next;
            cur = cur->next->next;
        }
        cur = head;
        // 新链表的头节点
        RandomListNode* copyhead = new RandomListNode(0);
        RandomListNode* copyhead1 = copyhead;
        //split为两个链表
        while(cur){
            copyhead->next = cur->next;
            cur->next = cur->next->next;
            
            copyhead = copyhead->next;
            cur = cur->next;
        }
        copyhead->next = NULL;
        return copyhead1->next;
    }
};

思路：

  • 第一遍遍历：
    将每个节点copy出来之后连接到该结点的后面。
    这样得到了两倍原本链表长度的链表。

  • 第二遍遍历：
    将每个原节点的random域复制到它之后的copy节点。

  • 第三遍遍历：
    将两个链表分离。
    原节点重新相链接，copy后的结点相链接。