aboutsummaryrefslogtreecommitdiff
path: root/copy_list_rand_ptr.py
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /copy_list_rand_ptr.py
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'copy_list_rand_ptr.py')
-rw-r--r--copy_list_rand_ptr.py60
1 files changed, 60 insertions, 0 deletions
diff --git a/copy_list_rand_ptr.py b/copy_list_rand_ptr.py
new file mode 100644
index 0000000..7909c0e
--- /dev/null
+++ b/copy_list_rand_ptr.py
@@ -0,0 +1,60 @@
+# 138. Copy List with 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.
+
+Construct a deep copy of the list. The deep copy should consist of exactly n
+brand new nodes, where each new node has its value set to the value of its
+corresponding original node. Both the next and random pointer of the new nodes
+should point to new nodes in the copied list such that the pointers in the
+original list and copied list represent the same list state. None of the
+pointers in the new list should point to nodes in the original list.
+
+For example, if there are two nodes X and Y in the original list, where
+X.random
+--> Y, then for the corresponding two nodes x and y in the copied list,
+x.random
+--> y.
+
+Return the head of the copied linked list.
+
+The linked list is represented in the input/output as a list of n nodes. Each
+node is represented as a pair of [val, random_index] where:
+
+ val: an integer representing Node.val
+ random_index: the index of the node (range from 0 to n-1) that the random
+pointer points to, or null if it does not point to any node.
+
+Your code will only be given the head of the original linked list.
+"""
+
+
+class Node:
+ def __init__(self, x, next=None, random=None):
+ self.val = int(x)
+ self.next = next
+ self.random = random
+
+
+class Solution:
+ def copyRandomList(self, head):
+ cache = {}
+ new_ptr = curr = Node(-1)
+ while head:
+ if head in cache:
+ newnode = cache[head]
+ else:
+ newnode = Node(head.val)
+ cache[head] = newnode
+ new_ptr.next = newnode
+ new_ptr = new_ptr.next
+ if head.random:
+ if head.random in cache:
+ new_random = cache[head.random]
+ else:
+ new_random = Node(head.random.val)
+ cache[head.random] = new_random
+ new_ptr.random = new_random
+ head = head.next
+ return curr.next