Source: InterviewBit – Copy List

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or NULL.

Return a deep copy of the list.

Example

Given list

   1 -> 2 -> 3

with random pointers going from

  1 -> 3
  2 -> 1
  3 -> 1

You should return a deep copy of the list. The returned answer should not contain the same node as the original list, but a copy of them. The pointers in the returned list should not link to any node in the original input list.

老實說筆者完全看不懂這題目到底想幹嘛，翻了許多人留的解釋後才稍稍有點概念：輸入值是一個連結串列但除了連結串列資料必備的 node.next 外還有一個隨機的連接節點 node.random ，而題目要求複製一個完全相同但獨立於輸入值的連結串列（也就是python的deepcopy功能。只是這功能並無法用於連結串列上，因在沒有建立全新節點的情況下，無論怎麼複製這些指代都會通往同一個連結串列，也因此對節點所做的資料修改會同步影響到所有的指定變數。）。

在確定題目要的是甚麼之後，剩下的就比較簡單了：建立一個 hashmap 儲存 node, node.next, 以及 node.random，並視連結串列的推進情況對當前節點進行對應及更新。

Code:

# Definition for singly-linked list with a random pointer.
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution:
    # @param head, a RandomListNode
    # @return a RandomListNode
    def copyRandomList(self, head):
        cache = {}
        curr = head
        while(curr):
            if curr not in cache:
                cache[curr] = RandomListNode(curr.label)
            
            if curr.next:
                if curr.next not in cache:
                    cache[curr.next] = RandomListNode(curr.next.label)
                cache[curr].next = cache[curr.next]
           
            if curr.random:
                if curr.random not in cache:
                    cache[curr.random] = RandomListNode(curr.random.label)
                cache[curr].random = cache[curr.random]
           
            curr = curr.next
        return cache[head]

GitHub: GitHub

發表留言