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.

Solution1:Two pass(copy + random) Hashmap

思路:
(1)先處理元素本值復(fù)制部分: 遍歷原list(nodes_src),對應(yīng)建立(復(fù)制)一個新的list(nodes_copy)策治,節(jié)點分別復(fù)制管宵;
遍歷過程中,建立一個map(node_src -> node_copy)赂韵,用來后續(xù)處理random
(2)random部分的復(fù)制: 同步遍歷list_src 和 list_copy, node_copy的random為 其(node_copy)對應(yīng)的node_src的random對應(yīng)(src->映射map->copy)的node_copy
實現(xiàn)1a: 建立新list的時候直接先連起來,更快些
(實現(xiàn)1b: 不先連,在第二次遍歷的時候通過get(node_src->node_copy)來找node_copy再連接宏娄,代碼看起來簡潔毙石,但速度慢)

Time Complexity: O(N) Space Complexity: O(N)

Solution2:依次在旁邊復(fù)制 連好random 再剝離

思路:Solution1中用hashmap是為了解決random時的node_src->node_copy的對應(yīng)問題廉沮,是因為否則在遍歷后我們無法訪問到該copy中的random結(jié)點。
方法二先將node_copy在原list中復(fù)制徐矩,-> src -> [copy] -> src -> [copy] -> src -> [copy] -> ...滞时,
這樣一來在遍歷的過程中,因為node_copy和node_src在同一list中滤灯,node_copy(即cur_src.next).random 就是cur_src.random.next(找到random對應(yīng)的copy結(jié)點);
最后再extract the copy list 即可
Time Complexity: O(N) Space Complexity: O(1)

Solution1a Code:

public class Solution {
    public RandomListNode copyRandomList(RandomListNode src_head) {
        if(src_head == null) return null;

        HashMap<RandomListNode, RandomListNode> node_map = new HashMap<>();

        // first traversal
        // (1)build a new node list by deeply copying from node_src
        // (2)build node_map mapping node_src -> node_copy for every node_src
        RandomListNode dummy_copy = new RandomListNode(0);
        RandomListNode cur_src = src_head;
        RandomListNode prev_copy = dummy_copy;
        while(cur_src != null) {
            RandomListNode node_copy = new RandomListNode(cur_src.label);
            prev_copy.next = node_copy;

            node_map.put(cur_src, node_copy);

            cur_src = cur_src.next;
            prev_copy = node_copy;
        }

        // second traversal
        // to add random ptr for each node_copy, by checking the map about which node_copy
        // (by corresponding node_src random relationship) that every node_copy.random should points to
        cur_src = src_head;
        RandomListNode cur_copy = dummy_copy.next;
        while(cur_src != null) {
            cur_copy.random = node_map.get(cur_src.random);
            cur_src = cur_src.next;
            cur_copy = cur_copy.next;
        }

        return dummy_copy.next;
    }
}

Solution1b Code:

public class Solution {
    public RandomListNode copyRandomList(RandomListNode src_head) {
        if(src_head == null) return null;

        HashMap<RandomListNode, RandomListNode> node_map = new HashMap<>();

        // first traversal
        // build node_map mapping node_src -> node_copy for every node_src
        RandomListNode cur_src = src_head;
        while(cur_src != null) {
            RandomListNode node_copy = new RandomListNode(cur_src.label);
            node_map.put(cur_src, node_copy);
            cur_src = cur_src.next;
        }

        // second traversal
        // to add random ptr for each node_copy, by checking the map about which node_copy; and to link copy_nodes also by getting from map
        // (by corresponding node_src random relationship) that every node_copy.random should points to
        cur_src = src_head;
        while(cur_src != null) {
            node_map.get(cur_src).next = node_map.get(cur_src.next);
            node_map.get(cur_src).random = node_map.get(cur_src.random);
            cur_src = cur_src.next;
        }

        return node_map.get(src_head);
    }
}

Solution2 Code:

public class Solution {
    public RandomListNode copyRandomList(RandomListNode src_head) {
        if(src_head == null) return null;

        // First traversal: Make copy of each node
        // -> src -> [copy] -> src -> [copy] -> src -> [copy] -> ...
        RandomListNode cur_src = src_head;
        RandomListNode cur_src_next_save;
        while(cur_src != null) {
            cur_src_next_save = cur_src.next;
            
            RandomListNode node_copy = new RandomListNode(cur_src.label);
            cur_src.next = node_copy;
            node_copy.next = cur_src_next_save;
            
            cur_src = cur_src_next_save;
        }
        
        // Second traversal: assign random pointers for the copy nodes
        cur_src = src_head;
        while(cur_src != null) {
            if(cur_src.random != null) {
                cur_src.next.random = cur_src.random.next;
            }
            cur_src = cur_src.next.next;
        }
        
        // Third traversal: restore the original list, and extract the copy list.
        cur_src = src_head;
        RandomListNode dummy_copy = new RandomListNode(0);
        RandomListNode cur_copy = dummy_copy; 
        
        while(cur_src != null) {
            // extract the copy
            cur_copy.next = cur_src.next;
            cur_copy = cur_copy.next;
            
            // restore the original list
            cur_src.next = cur_src.next.next;
            cur_src = cur_src.next;
            
        }
        return dummy_copy.next; 
    }
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末坪稽,一起剝皮案震驚了整個濱河市曼玩,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌窒百,老刑警劉巖黍判,帶你破解...
    沈念sama閱讀 216,744評論 6 502
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異篙梢,居然都是意外死亡顷帖,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,505評論 3 392
  • 文/潘曉璐 我一進店門渤滞,熙熙樓的掌柜王于貴愁眉苦臉地迎上來贬墩,“玉大人,你說我怎么就攤上這事妄呕√瘴瑁” “怎么了?”我有些...
    開封第一講書人閱讀 163,105評論 0 353
  • 文/不壞的土叔 我叫張陵绪励,是天一觀的道長肿孵。 經(jīng)常有香客問我,道長优炬,這世上最難降的妖魔是什么颁井? 我笑而不...
    開封第一講書人閱讀 58,242評論 1 292
  • 正文 為了忘掉前任,我火速辦了婚禮蠢护,結(jié)果婚禮上雅宾,老公的妹妹穿的比我還像新娘。我一直安慰自己葵硕,他們只是感情好眉抬,可當我...
    茶點故事閱讀 67,269評論 6 389
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著懈凹,像睡著了一般蜀变。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上介评,一...
    開封第一講書人閱讀 51,215評論 1 299
  • 那天库北,我揣著相機與錄音,去河邊找鬼们陆。 笑死寒瓦,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的坪仇。 我是一名探鬼主播杂腰,決...
    沈念sama閱讀 40,096評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼椅文!你這毒婦竟也來了喂很?” 一聲冷哼從身側(cè)響起惜颇,我...
    開封第一講書人閱讀 38,939評論 0 274
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎少辣,沒想到半個月后凌摄,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,354評論 1 311
  • 正文 獨居荒郊野嶺守林人離奇死亡毒坛,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,573評論 2 333
  • 正文 我和宋清朗相戀三年望伦,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片煎殷。...
    茶點故事閱讀 39,745評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖腿箩,靈堂內(nèi)的尸體忽然破棺而出豪直,到底是詐尸還是另有隱情,我是刑警寧澤珠移,帶...
    沈念sama閱讀 35,448評論 5 344
  • 正文 年R本政府宣布弓乙,位于F島的核電站,受9級特大地震影響钧惧,放射性物質(zhì)發(fā)生泄漏暇韧。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 41,048評論 3 327
  • 文/蒙蒙 一浓瞪、第九天 我趴在偏房一處隱蔽的房頂上張望懈玻。 院中可真熱鬧,春花似錦乾颁、人聲如沸涂乌。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,683評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽湾盒。三九已至,卻和暖如春诅妹,著一層夾襖步出監(jiān)牢的瞬間罚勾,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,838評論 1 269
  • 我被黑心中介騙來泰國打工吭狡, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留尖殃,地道東北人。 一個月前我還...
    沈念sama閱讀 47,776評論 2 369
  • 正文 我出身青樓赵刑,卻偏偏與公主長得像分衫,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子般此,可洞房花燭夜當晚...
    茶點故事閱讀 44,652評論 2 354

推薦閱讀更多精彩內(nèi)容