LeetCode || Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.


思路1:最傻瓜的方法是首先遍历一次建立next关系的新list。然后第二次遍历处理random关系,对于每个有random结点的node,我们都从表头開始遍历寻找其random的结点。然后给新list的相应结点赋值。这种话对于每个node,寻找random须要花费O(N)时间。故总时间复杂度为O(N^2)。这个方案会超时。


思路2:改进思路1。假设处理random关系的复制,使其复杂度降为O(N)?答案是要找到原node的random指向的结点在新list中相应的那个结点,假设能一下找到,那么就攻克了;实现方法是使用一个map<old, new>。记录原node与新node的相应关系。然后进行两次遍历,第一次建立next关系的新list。第二次给新list建立random指向关系;代码例如以下:


/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        map<RandomListNode *, RandomListNode *> mapNodes;
        RandomListNode *newList = NULL;
        RandomListNode *newHead = NULL;
        RandomListNode *p = head;
        
        if(head==NULL)
            return NULL;
        while(p!=NULL){
            RandomListNode *q = new RandomListNode(p->label);
            mapNodes[p] = q;
            if(newHead==NULL){
                newHead = q;
                newList = q;   
            }
            else{
                newList->next = q;
                newList = newList->next;
            }
            p = p->next; 
        }
        p = head;
        newList = newHead;
        while(p!=NULL){
            if(p->random!=NULL)
                newList->random = mapNodes[p->random];      //注意这里要用p->random而不是p
            p = p->next;
            newList = newList->next;
        }
        return newHead;     //返回值是newHead而不是newList,由于此时newList指向尾部
    }
};


思路3:思路2没有改变原list结构,可是使用了map,故须要额外的内存空间,假设原list解构可变。那么能够不必使用map记录映射关系,而是直接把复制的node放在原node的后面,这样结构变为:

LeetCode || Copy List with Random Pointer


上面为第一次遍历,第二次遍历时把红色的新node的random域赋值。规则是:

newNode->ranodm = oldNode->random->next;

然后第三次遍历把上面的链表拆分为两个就可以。代码例如以下:


/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode *newList = NULL;
        RandomListNode *newHead = NULL;
        RandomListNode *p = head;
        
        if(head==NULL)
            return NULL;
        while(p!=NULL){
            RandomListNode *q = new RandomListNode(p->label);
            q->next = p->next;
            p->next = q;
            
            p = q->next;
        }
        
        p = head;
        while(p!=NULL){
            if(p->random != NULL)
                p->next->random = p->random->next;
            p = p->next->next;
        }
        
        p = head;
        
        while(p!=NULL && p->next!=NULL){    //注意这里的条件,首先要推断p是否为null
            if(p==head){
                newHead = p->next;
                newList = newHead;
            }
            else{
                newList->next = p->next;
                newList = newList->next;
            }
            p->next = newList->next;
            p = p->next;
        }
        
        return newHead;     //返回值是newHead而不是newList,由于此时newList指向尾部
    }
};

參考链接:http://www.2cto.com/kf/201310/253477.html




上一篇:剑指Offer(二十五):复杂链表的复制


下一篇:LeetCode-138-Copy List with Random Pointer