1 題目描述



簡單來說，就是要你複製出一個一樣的ListNode結構，而這個ListNode有一個random的參數，這個random參數是指向ListNode中的任意一個節點，這個節點可以是自己，也可以是其他節點。

2 解法

2.0 創建鍊錶

在開始前，我們總是得想辦法先做個測試資料吧…輸入是一個二維陣列，每個元素是一個list，第一個元素是值，第二個元素是random的index，如果是None就是None。

  • input: [[7, None], [13, 0], [11, 4], [10, 2], [1, 0]]
  • output: ListNode 鍊錶
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def createLinkedList(nums: List[List[int]]) -> ListNode:
    if not nums:
        return None

    random_dict = {}  # 存 node, random_index
    node_dict = {}    # 存 index, node

    # 初始化頭節點
    head = ListNode(nums[0][0])
    current = head
    node_dict[0] = head
    random_dict[head] = nums[0][1]

    # 迭代列表中的其餘元素並創建鏈表
    for index, num in enumerate(nums[1:], start=1):
        current.next = ListNode(num[0])
        current = current.next
        node_dict[index] = current
        random_dict[current] = num[1]

    # 處理 random
    for node in node_dict.values():
        random_index = random_dict[node]
        node.random = node_dict.get(random_index)

    return head

def print_node_list(node):
    while node:
        print(f"(val: {node.val}, random.val: {node.random.val if node.random else None}) -> ", end="")
        node = node.next
    print("None")

if __name__ == "__main__":
    l1 = [[7, None], [13, 0], [11, 4], [10, 2], [1, 0]]

    input = createLinkedList(l1)
    print_node_list(input)

會印出以下內容

1
2
3
4
5
6
(val:7, random.val:None) -> 
(val:13, random.val:7) -> 
(val:11, random.val:1) -> 
(val:10, random.val:11) -> 
(val:1, random.val:7) -> 
None

2.1 我的解法

一開始我想到因為要複製出一模一樣的 Node 後，並且有了所有的 Node，才可以開始處理 random 的問題，所以步驟如下：

  1. 做一個字典方便搜尋：先複製整個 node 並且存 new_node 進去 node_dict (key: index, value: node)
  2. 建立一個紀錄 random_index 的字典，會紀錄 new_node 的 index 對應到 random_node 的 index (key: node.index, value: random_node.index)
  3. 開始幫 new_node 塞 random based on random_index_dict
    • 在 random_index_dict 找 new_node.index 的 random.index
    • 在 node_dict 找 random.index 取出 value 也就是 random_node
    • 塞 random_node 到 new_node.random 裡面

1. O(n) 建立 idx -> random_idx 的字典

首先我要知道每個 index 的 random index 是多少，所以我先做一個函數 findRandomIndex 來找出每個 node 的 random index，並且存進字典裡面。
結果大概會類似這樣 {0: None, 1: 0, 2: 4, 3: 2, 4: 0}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def findRandomIndex(self, head: Optional[ListNode]) -> Dict[int, ListNode]:
    node_index_dict = {}    # key: node, value: node.index
    random_index_dict = {}  # key: node.index, value: random.index
    index = 0

    # 先塞好所有node的資料字典
    current = head
    while current:
        node_index_dict.__setitem__(current, index)
        index += 1
        current = current.next

    # 開始整理 每個 node 的 random_index (key: node, value: random.index)
    current = head
    index = 0
    while current:
        random_node = current.random
        random_index = node_index_dict.get(random_node) if node_index_dict.get(random_node) is not None else None

        random_index_dict.__setitem__(index, random_index)
        current = current.next
        index += 1

    return random_index_dict    # 回傳每個node 他的random所在的index (key:node, value:random.index) {0: None, 1: 0, 2: 4, 3: 2, 4: 0}

2. 複製整個 node O(n) & 塞 random node O(n)

接下來我會先處理整個 new_node 的建立，並且建立另一個字典 node_idct 可以記錄 key=index, value=new_node，這樣我就可以

  1. 使用 random_index_dict 找到當前 index 的 random index
  2. 然後根據 random_index 從 node_dict 中找到 node
  3. 就可以串起來了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def copyRandomList(self, head: Optional[ListNode]) -> Optional[ListNode]:

    random_index_dict = self.findRandomIndex(head)
    node_dict = {}

    # 1.  先做好所有node的dict (key: index, value: node)
    index = 0
    dummy = ListNode(-1)
    current = dummy
    while head:
        current.next = ListNode(head.val)
        node_dict.__setitem__(index, current.next)
        # 換下一個階段
        head = head.next
        current = current.next
        index += 1

    new_head = dummy.next
    dummy.next = None

    # 2.  開始幫 new_head 塞 random based on `random_index_dict`
    current = new_head
    index = 0
    while current:
        random_index_of_cur_index = random_index_dict.get(index)
        random_node = node_dict.get(random_index_of_cur_index)
        current.random = random_node
        current = current.next
        index += 1

    return new_head

2.2 使用 HashTable

這個做法也是建立 HashTable 但是沒有像我這麼笨，他是直接把 old_node 當作 key，new_node 當作 value。簡直天才！因為這樣不管是串 next 還是串 random 都只要拿 old_node 去找，就可以找到 new_node，然後開始串。

大概是這種感覺：

看看下面才幾行…就解決了這個問題！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def copyRandomList2(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if not head:
        return None
    old_to_new = {}

    # 1. 做好 新舊對應的 dict
    cur = head
    while cur:
        old_to_new[cur] = ListNode(cur.val)
        cur = cur.next

    cur = head
    while cur:
        # 2. 因為已經有一個全部的dict 所以可以容易地將 next 跟 random 串起來
        old_to_new[cur].next = old_to_new.get(cur.next)
        old_to_new[cur].random = old_to_new.get(cur.random)
        cur = cur.next

    return old_to_new[head]

3 總結

這題我是有想出來的，並且通過測試。我也想到要使用HashTable，但是我卻沒想到要使用 old_node 來當作 key，new_node 來當作 value，這樣就可以在找 random 的時候，直接找到 new_node 就可以了。這個解法真的很巧妙，超級厲害！