Deep copy a linked list with a random pointer
A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null. Return the head of a deep copy of the list, ie all new nodes and both the node.next and node.random pointers point to new nodes.
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
if not head:
return None
old_to_new = {}
curr = head
while curr:
old_to_new[curr] = Node(curr.val)
curr = curr.next
curr = head
while curr:
old_to_new[curr].next = old_to_new.get(curr.next)
old_to_new[curr].random = old_to_new.get(curr.random)
curr = curr.next
return old_to_new[head]class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
if not head:
return None
curr = head
while curr:
new_node = Node(curr.val, curr.next)
curr.next = new_node
curr = new_node.next
curr = head
while curr:
if curr.random:
curr.next.random = curr.random.next
curr = curr.next.next
old_head = head
new_head = head.next
curr_old = old_head
curr_new = new_head
while curr_old:
curr_old.next = curr_old.next.next
curr_new.next = curr_new.next.next if curr_new.next else None
curr_old = curr_old.next
curr_new = curr_new.next
return new_headRelated Problems
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Given the root of a binary tree, flatten the tree into a "linked list":
The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The "linked list" should be in the same order as a pre-order traversal of the binary tree.
Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.
A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.
Given the root of a binary tree, return the inorder traversal of its nodes' values.