前言

今天選擇的是top 100 liked，並與linked list相關的題目：138. Copy List with Random Pointer
。這題不難，屬於medium，再來順便複習指標的概念吧！

想法

這題的關鍵點/難點在於random指標的複製。扣除掉這點，就是非常單純的題目─假這沒有random指針，只有一般linked list的val跟next的話，只要遍歷原本的linked list，針對每個node，把它的val取出來創建新的node，然後移到node的next如法炮製，再把前一個node指到這一個node就可以了。用說的好像有點抽象，大概如下：

Node* cur = head;
Node* new_head=new Node(head->val);
Node* new_cur = new_head;
while(nullptr!=cur){
    cur = cur->next;
    Node* new_node = new Node(cur->val);
    new_cur->next = new_node;
    new_cur = new_cur->next;
}
return new_head;

但現在多了一個random，而且它是可能隨便指向任一個點，也有可能重複指到同一個點，要如何讓我們新的list的對應指標也能指到新的list中正確的位置呢？
仔細想一想，就會發現我們需要一個mapping表，可以從表中查到舊的node跟新的node對應的位置，這樣針對新的node在指向random的時候，我們就可以改指向對應的新node；例如說：原本的node x指向random是指向y這個node：x->random=y；那我們要改成新的node，就只要讓x->random=mapping(y)就行了。
採用這種策略，簡單的解法如下：

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*, Node*> m;
        Node* ptr = head;
        while (ptr) {
            m[ptr] =new Node(ptr->val);
            ptr = ptr->next;
        }
        ptr = head;
        while (ptr) {
            m[ptr]->next = m[ptr->next];
            m[ptr]->random = m[ptr->random];
            ptr = ptr->next;
        }
        return m[head];
    }
};

但不想要多花這個存mapping表的空間，我們可以優化成為不用mapping表的版本。要如何做到呢？我們可以讓原本的node可以指到新的node，如題目附的hint 3所說:

We can avoid using extra space for old node ---> new node mapping, by tweaking the original linked list. Simply interweave the nodes of the old and copied list. For e.g.
Old List: A --> B --> C --> D
InterWeaved List: A --> A' --> B --> B' --> C --> C' --> D --> D'

我將這個想法的實現拆成三大部分步驟，如下：

1. 創造新的node，並將其插入原linked list中
2. 讓新的node的random指向新的list的node對應的點(會是原本指向的node的next)
3. 把原本的linked list跟新的linked list拆開

實際程式碼如下：

/*
// 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* copyRandomList(Node* head) {
        if(nullptr==head){
            return head;
        }
        
        Node* cur = head;
        // create a new node for each node, and make the new node insert into the original nodes
        while(nullptr!=cur){
            Node* new_node = new Node(cur->val);
            new_node->next = cur->next;
            cur->next = new_node;
            cur = new_node->next;
        }
        
        // for the new nodes, make the random points to the new nodes
        cur = head;
        while(nullptr!=cur){
            if(nullptr!=cur->random)
            {
                cur->next->random = cur->random->next;
            }
            cur = cur->next->next;
        }
        
        // separate the original list and the new list
        cur = head;
        Node* new_head=cur->next;
        Node* tmp= cur->next;
        while(nullptr!=cur){
            cur->next = cur->next->next;
            // the last tmp->next will be nullptr
            if(nullptr!=tmp->next){
                tmp->next = tmp->next->next;
            }
            cur = cur->next;
            tmp = tmp->next;
        }

        return new_head;
    }
};

結語

終於到了挑戰的中點~ 時間過得很快，假期也剩下最後一天了QQ 好好休息再繼續衝刺吧~