題目描述

請實現 copyRandomList 函數，復制一個復雜鏈表。在復雜鏈表中，每個節點除了有一個 next 指針指向下一個節點，還有一個 random 指針指向鏈表中的任意節點或者 null。

• -10000 <= Node.val <= 10000
• Node.random 為空（null）或指向鏈表中的節點。
• 節點數目不超過 1000 。

題目樣例

示例

輸入

     

head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

輸出

[[7,null],[13,0],[11,4],[10,2],[1,0]]

題目思考

1. 如何處理 random 指針?

解決方案

思路

• 如果只有 next 指針的話很簡單, 我們只需要對每個節點新建一個相同值的節點, 并保持指向關系, 逐個遍歷過去即可
• 現在多了個 random 指針, 想要定位新的指向的節點, 一個比較自然的想法就是額外維護一個老節點到新節點的映射關系, 可以用字典來實現
• 第一遍遍歷, 就只關注 next 部分, 并建立好映射關系
• 第二遍遍歷, 考慮 random 部分, 找到對應的新鏈表的節點, 然后當前節點的 random 指針指向它即可

復雜度

• 時間復雜度         O(N)
• 每個節點只需要遍歷兩次
• 空間復雜度         O(N)
• 額外需要一個字典

代碼

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None
        maps = {}
        # 第一遍遍歷, 建立新的鏈表, 以及老節點到新節點的映射關系
        copyHead = Node(head.val)
        origin, copy = head, copyHead
        maps[origin] = copy
        while origin.next:
            # 新建下一個節點, 并建立next關系
            copy.next = Node(origin.next.val)
            origin = origin.next
            copy = copy.next
            maps[origin] = copy
        # 第二遍遍歷, 處理random指針部分
        origin, copy = head, copyHead
        while origin:
            if origin.random:
                # 如果老節點random指針指向非空的話, 就將當前新節點也指向隨機節點對應的新節點
                copy.random = maps[origin.random]
            origin = origin.next
            copy = copy.next
        return copyHead