LeetCode如何實現(xiàn)復雜鏈表的復制

題目描述

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

• -10000 <= Node.val <= 10000
• Node.random 為空（null）或指向鏈表中的節(jié)點。
• 節(jié)點數(shù)目不超過 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 指針的話很簡單, 我們只需要對每個節(jié)點新建一個相同值的節(jié)點, 并保持指向關(guān)系, 逐個遍歷過去即可
• 現(xiàn)在多了個 random 指針, 想要定位新的指向的節(jié)點, 一個比較自然的想法就是額外維護一個老節(jié)點到新節(jié)點的映射關(guān)系, 可以用字典來實現(xiàn)
• 第一遍遍歷, 就只關(guān)注 next 部分, 并建立好映射關(guān)系
• 第二遍遍歷, 考慮 random 部分, 找到對應的新鏈表的節(jié)點, 然后當前節(jié)點的 random 指針指向它即可

復雜度

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

代碼

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