剑指 Offer 35. 复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

思路1：利用哈希表来进行链表指针的存储

即将链表问题转换为数组，以便于直接存取

头文件的导入：#include<unordered_map>

代码：

class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        unordered_map<Node*,Node*>map;
        Node* cur = head;
        //哈希表存储链表
        while(cur){
            map[cur] = new Node(cur->val);
            cur = cur ->next;
        }
        //利用哈希表实现next和random
        cur = head;
        while(cur){
            map[cur]->next=map[cur->next];
            map[cur]->random= map[cur->random];
            cur = cur->next;
        }
        return map[head];

        
    }
};

思路2：

1. 复制一个新的节点在原有节点之后，如 1 -> 2 -> 3 -> null 复制完就是 1 -> 1 -> 2 -> 2 -> 3 - > 3 -> null
2. 从头开始遍历链表，通过 cur.next.random = cur.random.next 可以将复制节点的随机指针串起来，当然需要判断 cur.random 是否存在
3. 将复制完的链表一分为二 根据以上信息，我们不难写出以下代码

   class Solution {
       public Node copyRandomList(Node head) {
           if (head == null) {
               return head;
           }
           // 完成链表节点的复制
           Node cur = head;
           while (cur != null) {
               Node copyNode = new Node(cur.val);
               copyNode.next = cur.next;
               cur.next = copyNode;
               cur = cur.next.next;
           }
   
           // 完成链表复制节点的随机指针复制
           cur = head;
           while (cur != null) {
               if (cur.random != null) { // 注意判断原来的节点有没有random指针
                   cur.next.random = cur.random.next;
               }
               cur = cur.next.next;
           }
   
           // 将链表一分为二
           Node copyHead = head.next;
           cur = head;
           Node curCopy = head.next;
           while (cur != null) {
               cur.next = cur.next.next;
               cur = cur.next;
               if (curCopy.next != null) {
                   curCopy.next = curCopy.next.next;
                   curCopy = curCopy.next;
               }
           }
           return copyHead;
       }
   }