Home [Algorithm] Copy Linked List with Arbitrary Pointer
Post
Cancel

[Algorithm] Copy Linked List with Arbitrary Pointer

https://www.educative.io/m/copy-linked-list-with-arbitrary-pointer

문제

You are given a linked list where the node has two pointers. The first is the regular next pointer. The second pointer is called arbitrary_pointer and it can point to any node in the linked list. Your job is to write code to make a deep copy of the given linked list. Here, deep copy means that any operations on the original list (inserting, modifying and removing) should not affect the copied list.

풀이

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
def deep_copy_arbitrary_pointer(head):
  if head == None:
    return None

  current = head
  new_head = None
  new_prev = None
  ht = dict()

  # create copy of the linked list, recording the corresponding
  # nodes in hashmap without updating arbitrary pointer
  while current != None:
    new_node = LinkedListNode(current.data)

    # copy the old arbitrary pointer in the new node
    new_node.arbitrary = current.arbitrary

    if new_prev != None:
      new_prev.next = new_node
    else:
      new_head = new_node
    ht[current] = new_node # 🔑
    new_prev = new_node
    current = current.next

  new_current = new_head

  # updating arbitrary pointer
  while new_current != None:
    if new_current.arbitrary != None:
      node = ht[new_current.arbitrary] # 🔑
      new_current.arbitrary = node
    new_current = new_current.next

  return new_head

def create_linked_list_with_arb_pointers(length):
  head = create_random_list(length)
  v = []
  temp = head
  while temp != None:
    v.append(temp)
    temp = temp.next

  for i in range(0, len(v)):
    j = random.randint(0, len(v) - 1)
    p = random.randint(0, 100)
    if p < 75:
      v[i].arbitrary = v[j]

  return head

def print_with_arb_pointers(head):
  while head != None:
    print(str(head.data) + " (", end="")
    if head.arbitrary != None:
      print(head.arbitrary.data, end ="")
    print("), ", end="")
    head = head.next

# Test Program.
def main():
  head = create_linked_list_with_arb_pointers(9)
  print_with_arb_pointers(head)

  head2 = deep_copy_arbitrary_pointer(head)
  print_with_arb_pointers(head2)

https://github.com/restato/Algorithms/blob/master/Hash/copy_linked_list_with_arbitrary_pointer.py

정리

  • Runtime Complexity: Linear, O(n)
  • Memory Complexity: Linear, O(n)
This post is licensed under CC BY 4.0 by the author.

[Python] Postgresql Connection

[Algorithm] Find the missing number in the array