复制带随机指针的链表

Leetcode Link: 剑指 Offer 35. 复杂链表的复制 - 力扣（LeetCode） 138. 复制带随机指针的链表 - 力扣（LeetCode）

题目

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

解法一

思路： 本题的难点，如何在遍历的时候保留 random 的指向信息。

用哈希表，表示为：dic[原节点] = 新节点

1. 先遍历，为每个原节点创建新的节点，并利用哈希表建立映射关系 dic[原节点] = 新节点
2. 在遍历一次，利用原节点的 next 和 random 来对新节点的 next 和 random 赋值。
3. 返回 dic[head]

可以看题解，更详细。

题解：

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return None
        dd = {}
        cur = head
        while(cur):
            dd[cur] = Node(cur.val)
            cur = cur.next
        
        cur = head
        while(cur):
	        # 下面两句可以简化，见下面的代码。
            dd[cur].next = dd[cur.next] if cur.next != None else None
            dd[cur].random = dd[cur.random] if cur.random != None else None
            cur = cur.next
        return dd[head]     

简化两句，用 dict.get()

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return None
        dic = {}
        # 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        cur = head
        while cur:
            dic[cur] = Node(cur.val)
            cur = cur.next
        cur = head
        # 4. 构建新节点的 next 和 random 指向
        while cur:
            dic[cur].next = dic.get(cur.next)
            dic[cur].random = dic.get(cur.random)
            cur = cur.next
        # 5. 返回新链表的头节点
        return dic[head]

解法二

思路： 还有一个原地的方法，后面在看吧。

题解：

解法三

思路：

题解：

启发和联系