Copy List With Random Indicator

发表于 | 分类于

CopyList(拷贝带有随机节点的链表)

题目描述：

给定一个链表节点结构的新定义，其中链表节点在包含下一个节点指针的情况下，还包含指向random的指针。其中指向random的指针可以指向任意在链表中的节点，或者为空。其定义如下。题目要求给定一个链表的头结点，其节点结构如定义中所诉。要求复制该链表，并返回新建链表的头结点。

1
2
3
4
5
6
7
#include <iostream>
struct randomListNode{
    int val;
    randomListNode* next;
    randomListNode* rand;
    randomListNode(int x): val(x), next(NULL), rand(NULL) {};
};

例子：

假设链表结构为如下:1->2->3->NULL。其中1节点的random指针指向3；2的random指针指向NULL；3的random指针指向2。

解题思路1：

解题的第一种思路是构造hash表。其中key是旧表的节点，value是与旧表节点值相同的新建节点。

key value
1 1’
2 2’
3 3’

然后我们不断遍历key的next指针，将value的next的指针连接；然后遍历key的random指针将value的关系连接。举例遍历到1的时候，我们检查1节点的random指针是3，则将1’的random指针指向3’即可。

解法1代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include "randonListNode.h"
#include <map>
class copyListWithRand1{
public:
    randomListNode* copyListWithRand(randomListNode* head){
        std :: map<randomListNode*, randomListNode*> HashTable;
        randomListNode* cur = head;
        while(cur != NULL){
            randomListNode* tmp = new randomListNode(cur->val);
            HashTable.insert({cur, tmp});
            cur = cur->next;
        }                  //构造hash表
        cur = head;
        while(cur != NULL){
            HashTable[cur]->next = HashTable[cur->next];
                          // 重新连接next指针
            HashTable[cur]->rand = HashTable[cur->rand];
                          //重新连接random指针
            cur = cur->next;
        }
      return HashTable[head];
    }
};

解法2的思路：

解法1的思路是利用hash表找到旧节点和新节点之间的关系，通过一个新的方式我们可以不用hash表的方式做到。主要的方法是我们通过1->2->3->NULL.来构建一个新的链表1->1’->2->2’->3->3’->NULL。这样我们就知道了新节点肯定在旧节点的next指针下。然后通过遍历旧节点的random指针改变新节点的random指针；再将这个链表拆分返回头结点即可。

解法2代码如下：

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
class copyListWithRand2{
public:
    randomListNode* copyListWithRand(randomListNode* head){
        if (head == NULL) {
            return head;
        }
        randomListNode* cur = head;
        while(cur != NULL){
            randomListNode* tmp = new randomListNode(cur->val);
            tmp->next = cur->next;
            cur->next = tmp;
            cur = cur->next->next;
        }                  //重新构造带有新旧节点的链表
        cur = head;
        while(cur != NULL){
            cur->next->rand = cur->rand == NULL ? NULL : cur->rand->next;
            cur = cur->next->next;
        }                // 改变random指针。注意判断指针是否为空
        cur = head->next;
        randomListNode* result = cur;
        while(head != NULL){
            head->next = head->next->next;
            cur->next = cur->next == NULL ? NULL : cur->next->next;                  // 拆分新旧链表的节点，也是注意判断空节点
            head = head->next;
            cur = cur->next;
        }
        return result;
    }
};