From d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa Mon Sep 17 00:00:00 2001 From: jack <0x6A73@pm.me> Date: Fri, 14 Jun 2024 13:13:15 -0600 Subject: initial --- copy_list_rand_ptr.py | 60 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 60 insertions(+) create mode 100644 copy_list_rand_ptr.py (limited to 'copy_list_rand_ptr.py') 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 -- cgit v1.2.3