leetcode138. Copy List with Random Pointer

Kross 發布于2019-08-16 10:47 / 2224人閱讀

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

題目要求

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

因為任意節點指針的值在一遍遍歷中是無法復制的。所以我們可以基本確定至少需要兩次遍歷才能夠充分的復制鏈表。那么在第一次遍歷的時候，我們采用什么樣的數據結構來記錄第一次遍歷的值呢？最直觀的思路是使用map，第一次遍歷時我們訪問next指針，將當前對象和當前對象的復制對象作為key-value值存入map中。第二次遍歷時，我們可以一邊調整復制對象的next指針，一邊調整復制對象的random指針，這兩個指針指向的都將是map中源對象的復制對象。所以可以在兩次遍歷后完成任務。

    public RandomListNode copyRandomList(RandomListNode head) {
        if(head==null) return null;
        Map map = new HashMap();
        RandomListNode temp = head;
        while(temp!=null){
            map.put(temp, new RandomListNode(temp.label));
            temp = temp.next;
        }
        
        temp = head;
        while(temp!=null){
            RandomListNode cur = map.get(temp);
            cur.next = map.get(temp.next);
            cur.random = map.get(temp.random);
            temp = temp.next;
        }
        return map.get(head);
    }

思路二：利用鏈表的特性

那么我們有沒有可能在不使用map的情況下通過舊節點實現對新節點的檢索？答案是肯定的。我們可以充分利用鏈表的特性來保存對新的復制節點的指針。第一圈遍歷時，我們可以將復制的節點插入至被復制的節點的后面。這樣我們就可以通過舊節點的next值找到新節點。在第二圈遍歷的時候，我們可以依次更新復制節點的random指針，將其指向新的復制節點。最后一圈遍歷，我們調整next指針，恢復原鏈表和塑造新鏈表。

    public RandomListNode copyRandomList2(RandomListNode head) {
        if(head==null) return null;
        RandomListNode current = head, copyHead = null, copyCurrent = null;
        
        while(current!=null){
            RandomListNode temp = new RandomListNode(current.label);
            temp.next = current.next;
            current.next = temp;
            current = current.next.next;
        }
        
        current = head;
        while(current!=null){
            if(current.random!=null){
                current.next.random = current.random.next;
            }
            current = current.next.next;
        }
        
        current = head;
        copyCurrent = copyHead = head.next;
        head.next = head.next.next;
        while(current != null){
            current.next = current.next.next;
            copyCurrent.next = copyCurrent.next.next;
            copyCurrent = copyCurrent.next;
            current = current.next;
        }
        return copyHead;
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

云服務器 GPU云服務器 Pointer 138vps ddd138 Leetcod

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

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

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
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
[Leetcode] Copy List with Random Pointer 復制隨機指針

摘要：棧迭代復雜度時間空間如果不算新鏈表的空間則是思路由于隨機指針有可能產生環路，我們不能直接沿著隨機指針的方向一個一個復制。同時我們又不能沿著指針直接復制，因為我們不知道隨機指針所指向的新節點是哪個。 Copy List with Random Pointer A linked list is given such that each node contains an additiona...

Olivia 2019-08-14 12:25 評論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