Copy List Wirh Random Pointer

Description

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.

Example

Challenge:
Could you solve it with O(1) space?

Deep copy the list using the next pointer, then scan the list connect the random pointer, finally disconnect the origin list and copied list.

Link

Lintcode_ladder

Method

1. hash table o(n) s(n)
2. use next pointer to create duplicate copy, o(n) s(1)

Example

1. 1

```c++ /**

• 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) { // write your code here if (!head) {

     return nullptr;
    

    } unordered_map dict; RandomListNode dummy(0); RandomListNode prev = &dummy; RandomListNode cur = nullptr; while (head) {

     if (dict.find(head) != dict.end()) {
         cur = dict.find(head)->second;
     } else {
         cur = new RandomListNode(head->label);
         dict[head] = cur;
     }
     prev->next = cur;
    

        if (head->random) {
            if (dict.find(head->random) != dict.end()) {
                cur->random = dict.find(head->random)->second;
            } else {
                cur->random = new RandomListNode(head->random->label);
                dict[head->random] = cur->random;
            }
        }
        prev = prev->next;
        head = head->next;
    }
    return dummy.next;
}

}; ```

Similar problems

x

Tags

x