摘要:給定一個鏈表,每個節點包含一個額外增加的隨機指針,該指針可以指向鏈表中的任何節點或空節點。要求返回這個鏈表的深拷貝。提示你必須返回給定頭的拷貝作為對克隆列表的引用。確定隨機節點的關系之后再拆分鏈表。其時間復雜度為,空間復雜度為。
給定一個鏈表,每個節點包含一個額外增加的隨機指針,該指針可以指向鏈表中的任何節點或空節點。
要求返回這個鏈表的深拷貝。
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.
示例:
輸入: {"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1} 解釋: 節點 1 的值是 1,它的下一個指針和隨機指針都指向節點 2 。 節點 2 的值是 2,它的下一個指針指向 null,隨機指針指向它自己。
提示:
你必須返回給定頭的拷貝作為對克隆列表的引用。
Note:
You must return the copy of the given head as a reference to the cloned list.
解題思路:由于需要考慮隨機指針,隨機指針指向的節點可能是null,也可能是鏈表的最后一個節點,深拷貝下,你不能將新鏈表的隨機指針指向原鏈表的節點,所以無法一遍得到新鏈表。
兩種解題方法,一種是拷貝所有節點,暫存在一種數據結構內,然后再遍歷一遍該數據結構,找到拷貝的節點,確定隨機指針的指向。因為每個節點都要找到隨機指針指向的節點,如果借助 散列表(字典) 其查找復雜度為 O(1) ,這樣可以把總時間復雜度降到 O(n) ,由于要暫存所有節點,其空間復雜度為 O(n)。
另一種解題方法是需要三次遍歷得到結果,簡單來說就是先把每個節點拷貝,并把拷貝節點連接到原節點后面,依次類推。確定隨機節點的關系之后再拆分鏈表。是一種很巧妙的思路:
原鏈表:1->2->3
復制每個節點到原節點后面:1->1->2->2->3->3
復制隨機指針的指向關系
拆分鏈表:1->2->3, 1->2->3
復制隨機指針指向時,原節點的隨機節點下一個節點即為新節點的隨機節點。假如原鏈表:1->2->3,節點1的隨機節點為3,復制節點之后:1->1->2->2->3->3
我們只需將新節點(原節點1的后一個節點1)指向原節點的隨機節點的后一個節點(原節點的隨機節點為3,而復制之后隨機節點3的后一個節點依然為3,但這個節點為新節點),最后拆分鏈表(鏈表拆分不影響節點指向關系)。其時間復雜度為 O(n),空間復雜度為 O(1)。
第一種方法:Java:
class Solution { public Node copyRandomList(Node head) { if (head == null) return null; HashMapmap = new HashMap<>();//借助hashMap Node newHead = new Node(0);//虛擬頭節點 Node cur = newHead;//指針指向當前節點 Node tmp; while (head != null) { if (map.containsKey(head)) {//查詢原節點是否已存在于map tmp = map.get(head);//如果存在直接取value值 } else { tmp = new Node(head.val);//不存在則新建一個值相同的節點 map.put(head, tmp);//存入map,key為原節點,value為新節點 } cur.next = tmp; if (head.random != null) {//原節點的隨機節點不為空的情況下 if (map.containsKey(head.random)) {//查詢該隨即節點是否已存在于map tmp.random = map.get(head.random);//存在則直接將新節點的隨機指針指向其value值 } else { tmp.random = new Node(head.random.val);//不存在則新建一個值相同的隨機節點 map.put(head.random, tmp.random);//存入map,key為原節點的隨機節點,value為新節點的隨機節點 } } head = head.next;//刷新原鏈表當前頭節點 cur = tmp;//即cur=cur.next,刷新新鏈表當前節點 } return newHead.next; } }
Python3:
class Solution: def copyRandomList(self, head: "Node") -> "Node": if not head: return None map = {} newHead = Node(val=0, next=None, random=None) cur = newHead while head: if head in map.keys(): tmp = map.get(head) else: tmp = Node(val=head.val, next=None, random=None) map.setdefault(head, tmp) cur.next = tmp if head.random: if head.random in map.keys(): tmp.random = map.get(head.random) else: tmp.random = Node(val=head.random.val, next=None, random=None) map.setdefault(head.random, tmp.random) head = head.next cur = tmp return newHead.next第二種方法:
Java:
class Solution { public Node copyRandomList(Node head) { if (head == null) return null; //復制節點 1->2->3 ==> 1->1->1->2->2->3->3 Node cur = head; while (cur != null) { Node next = cur.next; Node tmp = new Node(cur.val); cur.next = tmp; tmp.next = next; cur = next; } //復制隨機指針 cur = head; while (cur != null) { //cur.next.random=>新節點的隨機節點 cur.random.next=>原節點的隨機節點的下一個節點 cur.next.random = cur.random == null ? null : cur.random.next; cur = cur.next.next;//鏈表擴展一倍后肯定是偶數位鏈表,所以可以直接用cur.next.next } //分離節點 cur = head; Node newHead = head.next;//新鏈表頭節點 while (cur != null) { Node tmp = cur.next; cur.next = tmp.next; cur = cur.next; tmp.next = cur == null ? null : cur.next; } return newHead; } }
Python3:
class Solution: def copyRandomList(self, head: "Node") -> "Node": if not head: return None cur = head while cur: next = cur.next tmp = Node(val=cur.val, next=next, random=None) cur.next = tmp cur = next cur = head while cur: cur.next.random = cur.random.next if cur.random else None cur = cur.next.next cur = head newHead = head.next while cur: tmp = cur.next cur.next = tmp.next cur = cur.next tmp.next = cur.next if cur else None return newHead
歡迎關注微.信公.眾號一起學習:愛寫Bug
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/75626.html
摘要:給定一個鏈表,每個節點包含一個額外增加的隨機指針,該指針可以指向鏈表中的任何節點或空節點。要求返回這個鏈表的深拷貝。提示你必須返回給定頭的拷貝作為對克隆列表的引用。確定隨機節點的關系之后再拆分鏈表。其時間復雜度為,空間復雜度為。 給定一個鏈表,每個節點包含一個額外增加的隨機指針,該指針可以指向鏈表中的任何節點或空節點。 要求返回這個鏈表的深拷貝。 A linked list is g...
摘要:題目要求假設存在這樣一個鏈表,在鏈表的每一個節點中,除了記錄了自身值和指向下一個節點的指針,還有一個隨機指針指向鏈表中任意一個節點。所以可以在兩次遍歷后完成任務。最后一圈遍歷,我們調整指針,恢復原鏈表和塑造新鏈表。 題目要求 A linked list is given such that each node contains an additional random pointer ...
摘要:解題思路涉及到圖的遍歷無非就是深度優先搜索廣度優先搜索,可以先看前幾日的這篇文章就需要借助隊列實現,可以借助棧也可以直接用遞歸實現。 題目: 給定無向連通圖中一個節點的引用,返回該圖的深拷貝(克隆)。圖中的每個節點都包含它的值 val(Int) 和其鄰居的列表(list[Node])。 Given a reference of a node in a connected undirec...
摘要:棧迭代復雜度時間空間如果不算新鏈表的空間則是思路由于隨機指針有可能產生環路,我們不能直接沿著隨機指針的方向一個一個復制。同時我們又不能沿著指針直接復制,因為我們不知道隨機指針所指向的新節點是哪個。 Copy List with Random Pointer A linked list is given such that each node contains an additiona...
閱讀 3296·2021-11-24 09:39
閱讀 2805·2021-10-12 10:20
閱讀 1908·2019-08-30 15:53
閱讀 3076·2019-08-30 14:14
閱讀 2600·2019-08-29 15:36
閱讀 1121·2019-08-29 14:11
閱讀 1956·2019-08-26 13:51
閱讀 3408·2019-08-26 13:23