Solution to Copy List with Random Pointer by LeetCode

Question: https://oj.leetcode.com/problems/copy-list-with-random-pointer/

Question Name: Copy List with Random Pointer

Quite similar with the Clone Graph by LeetCode.

# Definition for singly-linked list with a random pointer.

# class RandomListNode:

# def __init__(self, x):

# self.label = x

# self.next = None

# self.random = None

class Solution:

# @param head, a RandomListNode

# @return a RandomListNode

def copyRandomList(self, head):

# Store the mapping between old nodes and new nodes

mapOldToNew ={None:None}

# Clone all the old nodes with only labels.

current = head

while current != None:

mapOldToNew[current] = RandomListNode(current.label)

current = current.next

# Assign the next and random of new cloned nodes.

current = head

while current != None:

mapOldToNew[current].next = mapOldToNew[current.next]

mapOldToNew[current].random = mapOldToNew[current.random]

current = current.next

# Return the cloned head

return mapOldToNew[head]

Happy Father’s Day!

namespace CopyListWithRandomPointer {

struct RandomListNode {

int label;

RandomListNode *next, *random;

RandomListNode(int x) : label(x), next(nullptr), random(nullptr) {}

};

class Solution {

public:

//O(N) time, 2 runs, O(1) space, the original list will be changed

RandomListNode *copyRandomList1(RandomListNode *head) {

RandomListNode *newhead = nullptr, *itor = head, *newitor = nullptr, *t = nullptr;

if (head != nullptr) {

while (itor != nullptr) {

t = new RandomListNode(itor->label);

if (newhead == nullptr)newhead = newitor = t;

else {

newitor->next = t;

newitor = newitor->next;

}

newitor->random = itor->random;

itor->random = newitor;

itor = itor->next;

}

newitor = newhead, itor = head;

while (newitor != nullptr) {

if (newitor->random != nullptr)

newitor->random = newitor->random->random;

newitor = newitor->next;

}

return newhead;

}

//O(N) time, 2 runs, O(1) space, the original list can be restored

RandomListNode *copyRandomList(RandomListNode *head) {

RandomListNode *newhead = nullptr, *itor = head, *newitor = nullptr, *t = nullptr;

if (head != nullptr) {

while (itor != nullptr) {

newitor = new RandomListNode(itor->label);

t = itor->next;

itor->next = newitor;

newitor->next = t;

itor = t;

}

itor = head;

while (itor != nullptr && itor->next != nullptr) {

if (itor->random != nullptr)

itor->next->random = itor->random->next;

itor = itor->next->next;

}

itor = head;

while (itor != nullptr && itor->next != nullptr) {

if (newhead == nullptr) {

newhead = itor->next;

newitor = newhead;

}

else {

newitor->next = itor->next;

newitor = newitor->next;

}

itor->next = itor->next->next;

itor = itor->next;

}

return newhead;

}

};

}

Solution to Copy List with Random Pointer by LeetCode

One Reply to “Solution to Copy List with Random Pointer by LeetCode”

Leave a Reply Cancel reply