LeetCode[138] Copy List with Random Pointer
MapA 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
復雜度
O(N), O(N)
思路
和clone graph一樣的思路。先copy順序的,再copy那些random的pointer.
代碼
public RandomListNode copyRandomList(RandomListNode node) { Mapmap = new HashMap<>(); RandomListNode dummy = new RandomListNode(0); RandomListNode p = head, q = head; // used to connect the new list; RandomListNode phead = dummy; while(p != null) { RandomListNode cp = new RandomListNode(p.label); map.put(p, cp); p = p.next; phead.next = cp; phead = phead.next; } while(q != null) { map.get(q).random = map.get(q.random); q = q.next; } return dummy.next; }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/66136.html
摘要:題目要求假設存在這樣一個鏈表,在鏈表的每一個節點中,除了記錄了自身值和指向下一個節點的指針,還有一個隨機指針指向鏈表中任意一個節點。所以可以在兩次遍歷后完成任務。最后一圈遍歷,我們調整指針,恢復原鏈表和塑造新鏈表。 題目要求 A linked list is given such that each node contains an additional random pointer ...
摘要:給定一個鏈表,每個節點包含一個額外增加的隨機指針,該指針可以指向鏈表中的任何節點或空節點。要求返回這個鏈表的深拷貝。提示你必須返回給定頭的拷貝作為對克隆列表的引用。確定隨機節點的關系之后再拆分鏈表。其時間復雜度為,空間復雜度為。 給定一個鏈表,每個節點包含一個額外增加的隨機指針,該指針可以指向鏈表中的任何節點或空節點。 要求返回這個鏈表的深拷貝。 A linked list is g...
摘要:給定一個鏈表,每個節點包含一個額外增加的隨機指針,該指針可以指向鏈表中的任何節點或空節點。要求返回這個鏈表的深拷貝。提示你必須返回給定頭的拷貝作為對克隆列表的引用。確定隨機節點的關系之后再拆分鏈表。其時間復雜度為,空間復雜度為。 給定一個鏈表,每個節點包含一個額外增加的隨機指針,該指針可以指向鏈表中的任何節點或空節點。 要求返回這個鏈表的深拷貝。 A linked list is g...
摘要:棧迭代復雜度時間空間如果不算新鏈表的空間則是思路由于隨機指針有可能產生環路,我們不能直接沿著隨機指針的方向一個一個復制。同時我們又不能沿著指針直接復制,因為我們不知道隨機指針所指向的新節點是哪個。 Copy List with Random Pointer A linked list is given such that each node contains an additiona...
摘要:大體意思就是,先復制到,順便將所有的放在再復制所有的到,順便將所有的放在最后令,令,將和分離,返回的頭結點 Problem 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. ...
閱讀 3401·2021-10-08 10:15
閱讀 5449·2021-09-23 11:56
閱讀 1467·2019-08-30 15:55
閱讀 445·2019-08-29 16:05
閱讀 2725·2019-08-29 12:34
閱讀 2036·2019-08-29 12:18
閱讀 915·2019-08-26 12:02
閱讀 1650·2019-08-26 12:00