138_复制带随机指针的链表

类型：链表

• 138. 复制带随机指针的链表 💛

  https://leetcode-cn.com/problems/copy-list-with-random-pointer/

  ❓ 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

  💡 哈希表

  第一次遍历，在创建新链表结点的同时，建立新旧结点的哈希映射。旧结点为键，新结点为值。

  第二次遍历，完善 random 指针，根据哈希表中新旧结点的对应关系。

  xclass Solution:
      def copyRandomList(self, head: 'Node') -> 'Node':
          if not head:
              return None
          newList = Node(head.val)
          hashMap = {head: newList}
          preNewNode = newList
          oldNode = head.next
          while oldNode:
              newNode = Node(oldNode.val)
              hashMap[oldNode] = newNode
              preNewNode.next = newNode
              preNewNode = newNode
              oldNode = oldNode.next
          oldNode = head
          newNode = newList
          while oldNode and newNode:
              if oldNode.random:
                  newNode.random = hashMap[oldNode.random]
              oldNode = oldNode.next
              newNode = newNode.next
          return newList

  时间复杂度：O(n)，空间复杂度：O(1)

  💡 孵化

  我们直接在原链表上创建新结点，每个新建的拷贝结点都放在原结点的旁边。

  • 遍历原来的链表并拷贝每一个节点，将拷贝节点放在原来节点的旁边，创造出一个旧节点和新节点交错的链表。
  • 迭代这个新旧节点交错的链表，并用旧节点的 random 指针去更新对应新节点的 random 指针。比方说， B 的 random 指针指向 A ，意味着 B’ 的 random 指针指向 A’ 。
  • 现在 random 指针已经被赋值给正确的节点， next 指针也需要被正确赋值，以便将新的节点正确链接同时将旧节点重新正确链接。

  class Solution(object):
      def copyRandomList(self, head):
          """
          :type head: Node
          :rtype: Node
          """
          if not head:
              return head
  
          # Creating a new weaved list of original and copied nodes.
          ptr = head
          while ptr:
  
              # Cloned node
              new_node = Node(ptr.val, None, None)
  
              # Inserting the cloned node just next to the original node.
              # If A->B->C is the original linked list,
              # Linked list after weaving cloned nodes would be A->A'->B->B'->C->C'
              new_node.next = ptr.next
              ptr.next = new_node
              ptr = new_node.next
  
          ptr = head
  
          # Now link the random pointers of the new nodes created.
          # Iterate the newly created list and use the original nodes random pointers,
          # to assign references to random pointers for cloned nodes.
          while ptr:
              ptr.next.random = ptr.random.next if ptr.random else None
              ptr = ptr.next.next
  
          # Unweave the linked list to get back the original linked list and the cloned list.
          # i.e. A->A'->B->B'->C->C' would be broken to A->B->C and A'->B'->C'
          ptr_old_list = head # A->B->C
          ptr_new_list = head.next # A'->B'->C'
          head_old = head.next
          while ptr_old_list:
              ptr_old_list.next = ptr_old_list.next.next
              ptr_new_list.next = ptr_new_list.next.next if ptr_new_list.next else None
              ptr_old_list = ptr_old_list.next
              ptr_new_list = ptr_new_list.next
          return head_old

  时间复杂度：O(n)，空间复杂度：O(1)