[Day 15] Leetcode 138. Copy List with Random Pointer (C++)

前言

今天选择的是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 好好休息再继续冲刺吧~