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

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

此题目主要分为三步：

1. 将链表复制一份连接到原链表上
2. 修改新节点的random指针指向关系
3. 将新节点从原链表中取下来，采用尾插法连接成新的链表，并恢复原链表

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return head;
        //1.复制链表连接其后

        Node* cur = head;
        while(cur){
            Node* copynode = new Node(cur->val);
            copynode->next = cur->next;
            cur->next = copynode;
            cur = cur->next->next;
        }   

        //2.指向随机链表的指针
        cur = head;
        while(cur){
            Node* copy = cur->next;
            if(cur->random == nullptr)
                copy->random = nullptr;
            else 
                copy->random = cur->random->next;
                
            cur = cur->next->next;
        }

        //3.把复制的链表取下来
        cur = head;
        Node* newhead = nullptr,*newtail = nullptr;
        while(cur){
            Node* copy = cur->next;
            cur->next = copy->next;
            if(newhead == nullptr){
                newhead = newtail = copy;
            }else{
                newtail->next = copy;
                newtail=newtail->next;
            }
            cur = cur->next;
        }
        return newhead;
    }
};