diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /copy_list_rand_ptr.py | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'copy_list_rand_ptr.py')
-rw-r--r-- | copy_list_rand_ptr.py | 60 |
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 |