python实现leetcode之138. 复制带随机指针的链表

解题思路

两步走
1.复制正常的链，并记下老的节点与新节点的对应关系
2.根据新老对应关系，处理随机节点

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

代码

"""
# 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: 'Node') -> 'Node':
        chain, mp = clone(head)
        set_random_pointer(head, chain, mp)
        return chain


def set_random_pointer(old_chain, new_chain, mp):
    if old_chain:
        if old_chain.random:
            new_chain.random = mp[id(old_chain.random)]
        set_random_pointer(old_chain.next, new_chain.next, mp)


def clone(chain):
    if not chain: return None, {}
    rest, d = clone(chain.next)
    new_chain = Node(chain.val, rest)
    return new_chain, {id(chain): new_chain, **d}