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

题目链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer/
难度：中等

描述：
给你一个长度为n的链表，每个节点包含一个额外增加的随机指针random，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。深拷贝应该正好由n个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的next指针和random指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

提示：
节点数：[0, 1000]

题解

迭代

遍历链表，复制每个节点（复制的节点的random = None），将复制的节点插入到原节点的后面：

再次遍历，添加复制节点的random指针

最后分离两个链表

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""
class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        cur = head
        while cur is not None:
            new_node = Node(cur.val, cur.next, None)
            cur.next = new_node
            cur = cur.next.next
        cur = head
        while cur is not None:
            if cur.random is not None:
                cur.next.random = cur.random.next
            cur = cur.next.next
        dummy = Node(0, None, None)
        temp = dummy
        cur = head
        while cur is not None:
            temp.next = cur.next
            temp = temp.next
            cur.next = cur.next.next
            cur = cur.next
        return dummy.next

哈希表

建立一个哈希表，遍历链表，使key = original_node，value = new_node
再次遍历链表，给new_node加上next 和random

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""
class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if head is None:
            return None
        node_map = {}
        cur = head
        while cur is not None:
            new_node = Node(cur.val, None, None)
            node_map[cur] = new_node
            cur = cur.next
        cur = head
        while cur is not None:
            if cur.next is not None:
                node_map[cur].next = node_map[cur.next]
            if cur.random is not None:
                node_map[cur].random = node_map[cur.random]
            cur = cur.next
        return node_map[head]