面试题35. 复杂链表的复制

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

思路1：
hash法。用原链表节点索引新链表节点。
//遍历第一遍，把val值copy下来＆建立hash表。
//遍历第二遍，连接节点＆把randomcopy下来。
时间复杂度O（n）,空间复杂度O（n）。

//hash法
//遍历第一遍，把val值copy下来。
//遍历第二遍，把randomcopy下来
//hash表，用原链表节点索引新链表节点
class Solution {
public:
    Node* copyRandomList(Node* head) {

        if(!head) return NULL;

        map<Node*,Node*>listOldAndNew;
        listOldAndNew[NULL] = NULL;

        Node* cur = head;

        //建立新链表，赋val值，建立原链表与新链表的对应关系
        while(cur)
        {
            Node* copyNode = new Node(cur->val);
            listOldAndNew[cur] = copyNode;
            cur = cur->next;
        }

        cur = head;

        //由索引串联节点并给random赋值
        while(cur)
        {
            listOldAndNew[cur]->next = listOldAndNew[cur->next];
            listOldAndNew[cur]->random = listOldAndNew[cur->random];
            cur = cur->next;
        }

        return listOldAndNew[head];   
    }
};

思路2：
巧妙的原地拷贝。

//原地修改
//第一步：先在每一个节点之后复制一个相同的节点
//第二步：再通过cur->next->random = cur->random->next指定random节点
//第三步：通过cur->next = cur->next->next,cur = cur->next将一个链表分为两个链表

class Solution {
public:
    Node* copyRandomList(Node* head) {

        if(!head) return NULL;

        Node* cur = head;

        //节点原地复制
        while(cur)
        {
            Node* copyNode = new Node(cur->val);
            copyNode->next = cur->next;
            cur->next = copyNode;
            cur = copyNode->next;
        }

        cur = head;

        //给random赋值
        while(cur)
        {
            //if(cur->random == NULL)  cur->next->random = NULL;
            //cur->next->random = cur->random->next;
            if(cur->random != NULL)  cur->next->random = cur->random->next; //这样写更简洁
            cur = cur->next->next;
        }

        //拆分链表
        Node* curHead = head->next; //复制链表头结点
        
        cur = head; //辅助指针origin
        Node* curCopy = head->next; //辅助指针copy
        
        while(cur)
        {
            cur->next = cur->next->next; //原链表
            if(cur->next != NULL) curCopy->next = cur->next->next; //copy链表
            
            curCopy = curCopy->next;
            cur = cur->next;  
        }

        return curHead;
    }       
};

//除非if里可以返回，不然还是好好写ifelse
//一种简便写法
//链表可以复制两份份头节点，一份用于找头，另一份移动查找结点
//复制链表：定义全局指针，随着新建的结点不断移动即可