剑指offer 36- 复杂链表的复刻

请实现一个函数可以复制一个复杂链表。

在复杂链表中，每个结点除了有一个指针指向下一个结点外，还有一个额外的指针指向链表中的任意结点或者null。

注意：

• 函数结束后原链表要与输入时保持一致。

分析：
算法一：

1.把原链表的每个结点后面都接一个同样的结点
2.修改结点的random指针：p->next->random = p->random->next
3.定义一个虚拟头结点dummy，将复制的出来的结点串起来
总时间复杂度：O（N）

• 这种做法修改了原始链表

/**
 * Definition for singly-linked list with a random pointer.
 * struct ListNode {
 *     int val;
 *     ListNode *next, *random;
 *     ListNode(int x) : val(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        
        /*
        1.把原链表的每个结点后面都接一个同样的结点
        2.修改结点的random指针：p->next->random = p->random->next
        3.定义一个虚拟头结点dummy，将复制的出来的结点串起来
        总时间复杂度：O（N）
        */
        
        for (auto p = head; p;) {
            auto np = new ListNode(p->val);
            auto temp = p->next;
            p->next = np;
            np->next = temp;
            p = temp;
        }
        for (auto p = head; p; p = p->next->next) {
            if(p->random)
                p->next->random = p->random->next;
        }
        
        auto dummy = new ListNode(-1);
        auto cur = dummy;
        for(auto p = head; p; p=p->next) {
            cur->next = p->next;
            cur = cur->next;
            p = p->next;
        }
        
        return dummy->next;
    }
};

算法二：
借助哈希表
O(n)
使用hash存储 key = 源链表节点，value = 目标链表节点，遍历源链表，判断每个节点和random节点是否在hash表中，如果不存在则创建

/**
 * Definition for singly-linked list with a random pointer.
 * struct ListNode {
 *     int val;
 *     ListNode *next, *random;
 *     ListNode(int x) : val(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        unordered_map<ListNode*, ListNode*> hash;
        hash[nullptr] = nullptr;
        auto dummy = new ListNode(-1);
        auto cur = dummy;
        for(;head;head = head->next, cur= cur->next) {
            if(!hash.count(head)) hash[head] = new ListNode(head->val);
            if(!hash.count(head->random)) hash[head->random] = new ListNode(head->random->val);
            cur->next = hash[head];
            cur->next->random = hash[head->random];
        }
        return dummy->next;
    }
};