剑指offer——37复杂链表的复制

 1 //使用hash表将链表节点记录，其key为节点值，这样有个缺陷就是当有相同的节点值时，就不知道key对应的是哪个节点地址了
 2 class Solution01 {
 3 public:
 4     RandomListNode* Clone(RandomListNode* pHead)
 5     {
 6         unordered_map<int, RandomListNode*>map;
 7         RandomListNode *p, *q, *newHead = new RandomListNode(0);
 8         p = pHead;
 9         q = newHead;
10         while (p != nullptr)
11         {
12             q->next = new RandomListNode(p->label);
13             map[p->label] = q->next;
14             p = p->next;
15             q = q->next;
16         }
17         p = pHead;
18         q = newHead->next;
19         while (p != nullptr)
20         {
21             if (p->random != nullptr)
22                 q->random = map[p->random->label];
23             p = p->next;
24             q = q->next;
25         }
26         return newHead->next;
27     }
28 };
29 
30 //直接将复制的节点置于原节点后面，这样找random节点时，很方便，不需要额外空间
31 class Solution02 {
32 public:
33     RandomListNode* Clone(RandomListNode* pHead)
34     {
35         if (pHead == nullptr)return nullptr;
36         RandomListNode *p = pHead, *q = nullptr, *newHead = new RandomListNode(0);
37         while (p != nullptr)//复制主链表
38         {
39             RandomListNode *q = new RandomListNode(p->label);
40             q->next = p->next;
41             p->next = q;
42             p = q->next;
43         }
44         p = pHead;
45         while (p != nullptr)//复制随机节点
46         {
47             if (p->random != nullptr)
48                 p->next->random = p->random->next;//原链表指向哪，那么新链表就指向其后面
49             p = p->next->next;
50         }
51         p = pHead;
52         q = newHead;
53         while (p!=nullptr)//取出复制链表，并还原链表
54         {
55             q->next = p->next;//取新链表
56             p->next = p->next->next;//还原原链表
57             p = p->next;
58             q = q->next;            
59         }
60         return newHead->next;
61     }
62 };