[Leetcode] Copy List with Random Pointer 復制隨機指針

Olivia 發布于2019-08-14 12:25 / 2652人閱讀

摘要：棧迭代復雜度時間空間如果不算新鏈表的空間則是思路由于隨機指針有可能產生環路，我們不能直接沿著隨機指針的方向一個一個復制。同時我們又不能沿著指針直接復制，因為我們不知道隨機指針所指向的新節點是哪個。

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.

棧迭代 復雜度

時間 O(N) 空間 O(N) 如果不算新鏈表的空間則是O(1)

思路

由于隨機指針有可能產生環路，我們不能直接沿著隨機指針的方向一個一個復制。同時我們又不能沿著next指針直接復制，因為我們不知道隨機指針所指向的新節點是哪個。這里有個技巧，我們把復制的表一對一的插在舊表的每個節點后面，這樣在第二次遍歷鏈表時，我們就肯定知道隨機指針指向的新節點是哪個了，肯定是舊節點隨即指針指向的舊節點的下一個節點。然后我們再遍歷一遍，把新舊兩個鏈表分割開來就行了。

代碼

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head==null) return null;
        RandomListNode n1 = head;
        RandomListNode n2;
        // 生成新節點并接在舊節點后面
        while(n1!=null){
            n2 = new RandomListNode(n1.label);
            n2.next = n1.next;
            n1.next = n2;
            n1 = n1.next.next;
        }
        // 給新節點的random字段賦值
        n1 = head;
        n2 = n1.next;
        while(n1!=null){
            n2.random = n1.random != null ? n1.random.next : null;
            n1 = n1.next.next;
            n2 = n1 != null ? n2.next.next : null;
        }
        n1 = head;
        n2 = n1.next;
        RandomListNode res = n2;
        // 將新舊節點分開
        while(n1!=null){
            n1.next = n1.next.next;
            n2.next = n2.next != null ? n2.next.next : null;
            n1 = n1.next;
            n2 = n2.next;
        }
        return res;
    }
}

GPU云服務器云服務器 random隨機數 random生成隨機數隨機數math_random Pointer

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64463.html

leetcode138. Copy List with Random Pointer

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

Kross 2019-08-16 10:47 評論0 收藏0
LeetCode 138：復制帶隨機指針的鏈表 Copy List with Random Poin

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

entner 2019-08-19 10:13 評論0 收藏0
LeetCode 138：復制帶隨機指針的鏈表 Copy List with Random Poin

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

Lucky_Boy 2019-07-31 11:31 評論0 收藏0
[LintCode/LeetCode] Copy List with Random Pointer

摘要：大體意思就是，先復制到，順便將所有的放在再復制所有的到，順便將所有的放在最后令，令，將和分離，返回的頭結點 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 評論0 收藏0
LeetCode[138] Copy List with Random Pointer

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 t...

novo 2019-08-14 15:57 評論0 收藏0