2023/3/4[LC:Random_List_Copy]

1>心得：

• 写“for"循环之前需要首先思考循环目的和结束条件；例如链表的遍历等；
• 模拟仔细；

2>思路

首先如果是单纯复制一个普通链表：

需要给前一个copy结点留一个pre指针；以便：pre->next=copy;

3>解法

此题有两个解法

问题的关键在于如何解决指向与当前结点相距不定的”复杂节点“;(如果是正常链表可以留一个pre指针)

解法一：通过HashMap记录对应新旧结点关系

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class solution{
    public Node* copy_random_list(Node* head){
        if(!head) return nullptr;
        map<Node*,Node*> map;
        for(Node* p=head;p;p=p->next){
            map.put(p,new Node(p->val));
        }
/*关键for循环*/
        for(Node* q=head;q;q=q->next){
            map.find(q)->second->next=map.get(q->next)->second;
            map.get(q)->second->random=map.get(q->random)->second;
        }
        return map.get(head)->second;
    }
}

解法二：原地重复链表记录新旧关系

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head){
            return nullptr;
        }
        for(Node* p=head;p!=nullptr;p=p->next->next){
            Node* new_p=new Node(p->val);
            new_p->next=p->next;
            p->next=new_p;
        }
/*关键for循环*/
        for(Node* p=head;p!=nullptr;p=p->next->next){
            if(p->random){
                p->next->random=p->random->next;//保证是复制的random结点
            }
        }
        Node* ans =head->next;
        Node* q=head;
        Node* r=head->next;
/*q直到null才停，r一次跳两步最后一步会r->null->next报错*/
        for(;r&&r->next&&q;r=r->next,q=q->next){
            q->next=q->next->next;
            r->next=r->next->next;
        }
        q->next=nullptr;
        r->next=nullptr;
        return ans;
    }
};