LeetCode[138] Copy List with Random Pointer

novo 發(fā)布于2019-08-14 15:57 / 1602人閱讀

LeetCode[138] Copy List with Random Pointer

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

Map

復(fù)雜度
O(N), O(N)

思路
和clone graph一樣的思路。先copy順序的，再copy那些random的pointer.

代碼

public RandomListNode copyRandomList(RandomListNode node) {
    Map map = 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;
}

GPU云服務(wù)器云服務(wù)器 Pointer LeetCode 138vps ddd138

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/66136.html

相關(guān)文章

leetcode138. Copy List with Random Pointer

摘要：題目要求假設(shè)存在這樣一個(gè)鏈表，在鏈表的每一個(gè)節(jié)點(diǎn)中，除了記錄了自身值和指向下一個(gè)節(jié)點(diǎn)的指針，還有一個(gè)隨機(jī)指針指向鏈表中任意一個(gè)節(jié)點(diǎn)。所以可以在兩次遍歷后完成任務(wù)。最后一圈遍歷，我們調(diào)整指針，恢復(fù)原鏈表和塑造新鏈表。題目要求 A linked list is given such that each node contains an additional random pointer ...

Kross 2019-08-16 10:47 評(píng)論0 收藏0
LeetCode 138：復(fù)制帶隨機(jī)指針的鏈表 Copy List with Random Poin

摘要：給定一個(gè)鏈表，每個(gè)節(jié)點(diǎn)包含一個(gè)額外增加的隨機(jī)指針，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)。要求返回這個(gè)鏈表的深拷貝。提示你必須返回給定頭的拷貝作為對(duì)克隆列表的引用。確定隨機(jī)節(jié)點(diǎn)的關(guān)系之后再拆分鏈表。其時(shí)間復(fù)雜度為，空間復(fù)雜度為。給定一個(gè)鏈表，每個(gè)節(jié)點(diǎn)包含一個(gè)額外增加的隨機(jī)指針，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)。要求返回這個(gè)鏈表的深拷貝。 A linked list is g...

entner 2019-08-19 10:13 評(píng)論0 收藏0
LeetCode 138：復(fù)制帶隨機(jī)指針的鏈表 Copy List with Random Poin

摘要：給定一個(gè)鏈表，每個(gè)節(jié)點(diǎn)包含一個(gè)額外增加的隨機(jī)指針，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)。要求返回這個(gè)鏈表的深拷貝。提示你必須返回給定頭的拷貝作為對(duì)克隆列表的引用。確定隨機(jī)節(jié)點(diǎn)的關(guān)系之后再拆分鏈表。其時(shí)間復(fù)雜度為，空間復(fù)雜度為。給定一個(gè)鏈表，每個(gè)節(jié)點(diǎn)包含一個(gè)額外增加的隨機(jī)指針，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)。要求返回這個(gè)鏈表的深拷貝。 A linked list is g...

Lucky_Boy 2019-07-31 11:31 評(píng)論0 收藏0
[Leetcode] Copy List with Random Pointer 復(fù)制隨機(jī)指針

摘要：棧迭代復(fù)雜度時(shí)間空間如果不算新鏈表的空間則是思路由于隨機(jī)指針有可能產(chǎn)生環(huán)路，我們不能直接沿著隨機(jī)指針的方向一個(gè)一個(gè)復(fù)制。同時(shí)我們又不能沿著指針直接復(fù)制，因?yàn)槲覀儾恢离S機(jī)指針?biāo)赶虻男鹿?jié)點(diǎn)是哪個(gè)。 Copy List with Random Pointer A linked list is given such that each node contains an additiona...

Olivia 2019-08-14 12:25 評(píng)論0 收藏0
[LintCode/LeetCode] Copy List with Random Pointer

摘要：大體意思就是，先復(fù)制到，順便將所有的放在再復(fù)制所有的到，順便將所有的放在最后令，令，將和分離，返回的頭結(jié)點(diǎn) 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. ...

Jacendfeng 2019-08-14 15:32 評(píng)論0 收藏0