Copy List with Random Pointer

leetcode.com

思路：

原來的linked list稱為old_ist，新的linked list稱為new_list

首先，可以直接一個一個copy old_list中的node，得到new_list，在這個過程中，可以先讓new_list中新得到的node的next指向old_list中相應node的next。同樣我們可以先讓新得到的random pointer指向old_list相應node的random pointer所指node。

這樣過完一遍之後，需要調整new_list的next和random pointer，從old_list換到相應的new_list的node，但是現在問題來了，我們沒有新舊兩個list中對應的node之間的關聯。

所以上面的思路需要調整，為了把新舊兩個list中對應的node關聯起來，比如old_list中的A，A.next=B，A.random=C

new_list中A的copy是A，那麼可以創建A之後，讓A.next=A, A.next=B, A.random=C

這樣過完一遍之後，還需要調整new_list的random，因為有了舊node到新node的指針，這個調整比較容易，只需

A.next.random = A.random.next

這樣之後，random pointer都對了，只需要把原來連在一起的old_list和new_list解開就好了。

代碼：

def copyRandomList(head): """ :type head: RandomListNode :rtype: RandomListNode """ if not head: return # create new_list p = head while p: new = RandomListNode(p.label) new.next = p.next new.random = p.random p.next = new p = new.next # make the random pointer of new_list correct p = head while p: if p.random: p.next.random = p.random.next p = p.next.next ans = head.next # return ans in the end old = head # old is head of old_list new = ans # new is head of new_list while old: old.next = new.next # make the next pointer of old_list correct if new.next: # if new.next is None, stop new.next = old.next.next new = new.next old = old.next else: break return ans

推薦閱讀：