2015年9月1日星期二

Lintcode: 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.
Have you met this question in a real interview? 
Yes

Example
Challenge
Could you solve it with O(1) space?
Tags Expand 
Hash Table Linked List

Thoughts: The basic solution is to copy a linked list. At the same time, use a hashmap to remember the mapping relation between two nodes of two linkedlists. (两个链表的结点间的对应关系）
Remember to copy the original random address of each node, which is the key of hashmap
Time: O(n)
Space: O(n)

Initial ugly codes:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 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:
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode *head2, *prev, *result, *initHead;
        result = NULL;
        head2 = NULL;
        initHead = head;
        unordered_map<RandomListNode*, RandomListNode*> hash;
        while(head){
            if(head2 == NULL) {
                head2 = new RandomListNode(head->label);
                head2->random = head->random;
                result = head2;
                hash[head] = head2;
                head = head->next;
                continue;
            }
            head2->next = new RandomListNode(head->label);
            head2->next->random = head->random;
            hash[head] = head2->next;
            head=head->next;
            head2=head2->next;
        }
        RandomListNode* p = result;
        while(p){
            p->random = hash[p->random];
            p = p->next;
        }
        return result;
        
    }
};

Modified version: change variable names and add dummy node
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 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:
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode * head2 = new RandomListNode(0);
        RandomListNode *result= head2;
        unordered_map<RandomListNode*, RandomListNode*> hash;
        while(head){
            head2->next = new RandomListNode(head->label);
            head2 = head2->next;
            head2->random = head->random;
            hash[head] = head2;
            head = head->next;
        }
        result = result->next;
        RandomListNode* p = result;
        while(p){
            p->random = hash[p->random];
            p=p->next;
        }
        return result;
    }
};

Space: O(1) solution:
Interesting!
Time:O(n)
Space:O(1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * 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:
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    RandomListNode *copyRandomList(RandomListNode *head) {
        if(head == NULL) return NULL;
        RandomListNode *result = head;
        while(head){
            RandomListNode* temp;
            temp = head->next;
            RandomListNode* node = new RandomListNode(head->label);
            node->random = head->random;
            
            head->next = node;
            node->next = temp;
            head=node->next;
        }
        result = result->next;
        RandomListNode *p = result;
        //Note: get random cannot be realized at the time with breaking linkedlists to get new list
        while(1){
            if(p->random != NULL)   p->random = p->random->next;
            if(p->next == NULL) break;
            p = p->next->next;
        }
        p = result;
        while(p->next != NULL){
            p->next = p->next->next;
            p = p->next;
        }
        return result;
    }
};



发帖者 时间：

没有评论:

发表评论

订阅： 博文评论 (Atom)