138. Copy List with Random Pointer
- Total Accepted: 81110
- Total Submissions: 308920
- Difficulty: Hard
- Contributors: Admin
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.
Code
# Definition for singly-linked list with a random pointer. # class RandomListNode(object): # def __init__(self, x): # self.label = x # self.next = None # self.random = None class Solution(object): def copyRandomList(self, head): """ :type head: RandomListNode :rtype: RandomListNode """ if head is None: return None # store copied nodes indexed by label copynodes = dict() copyhead = RandomListNode(head.label) head_bak = head copyhead_bak = copyhead # copy 'next' for each node while head.next: copyhead.next = RandomListNode(head.next.label) copynodes[head.next.label] = copyhead.next copyhead = copyhead.next head = head.next copyhead = copyhead_bak head = head_bak # copy 'random' for each node while head: if head.random: copyhead.random = copynodes[head.random.label] head = head.next copyhead = copyhead.next return copyhead_bak
Idea
Two rounds copy. In the first round, make sure node is copied and connected one by one. During the first round, also record newly copied nodes in a dictionary copynodes
. In the second round, copy field random
. You need to use the dictionary to locate the new copied nodes in constant time.
Note: This algorithm only works when no two nodes have the same label because we use node.label as keys in the dictionary.
More elegant way to utilize defaultdict:
# Definition for singly-linked list with a random pointer. # class RandomListNode(object): # def __init__(self, x): # self.label = x # self.next = None # self.random = None from collections import defaultdict class Solution(object): def copyRandomList(self, head): """ :type head: RandomListNode :rtype: RandomListNode """ d = defaultdict(lambda: RandomListNode(0)) d[None] = None tmp = head while tmp: d[tmp].label = tmp.label d[tmp].next = d[tmp.next] d[tmp].random = d[tmp.random] tmp = tmp.next return d[head]
Idea
d
is a defaultdict. The key of d is original node and the value is the copied node.
Another very convoluted way to solve this problem. Only constant extra space will be used: https://discuss.leetcode.com/topic/7594/a-solution-with-constant-space-complexity-o-1-and-linear-time-complexity-o-n/2