leetcode138. Copy List with Random Pointer

Kross 發(fā)布于2019-08-16 10:47 / 2293人閱讀

摘要：題目要求假設(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 which could point to any node in the list or null.

Return a deep copy of the list.

假設(shè)存在這樣一個(gè)鏈表，在鏈表的每一個(gè)節(jié)點(diǎn)中，除了記錄了自身值和指向下一個(gè)節(jié)點(diǎn)的指針，還有一個(gè)隨機(jī)指針指向鏈表中任意一個(gè)節(jié)點(diǎn)?，F(xiàn)在要求深度復(fù)制這份鏈表，在不改變原鏈表內(nèi)容的情況下，創(chuàng)建一組新的對象，該組對象中的值和原鏈表中的值相同。

思路一：map

因?yàn)槿我夤?jié)點(diǎn)指針的值在一遍遍歷中是無法復(fù)制的。所以我們可以基本確定至少需要兩次遍歷才能夠充分的復(fù)制鏈表。那么在第一次遍歷的時(shí)候，我們采用什么樣的數(shù)據(jù)結(jié)構(gòu)來記錄第一次遍歷的值呢？最直觀的思路是使用map，第一次遍歷時(shí)我們訪問next指針，將當(dāng)前對象和當(dāng)前對象的復(fù)制對象作為key-value值存入map中。第二次遍歷時(shí)，我們可以一邊調(diào)整復(fù)制對象的next指針，一邊調(diào)整復(fù)制對象的random指針，這兩個(gè)指針指向的都將是map中源對象的復(fù)制對象。所以可以在兩次遍歷后完成任務(wù)。

    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的情況下通過舊節(jié)點(diǎn)實(shí)現(xiàn)對新節(jié)點(diǎn)的檢索？答案是肯定的。我們可以充分利用鏈表的特性來保存對新的復(fù)制節(jié)點(diǎn)的指針。第一圈遍歷時(shí)，我們可以將復(fù)制的節(jié)點(diǎn)插入至被復(fù)制的節(jié)點(diǎn)的后面。這樣我們就可以通過舊節(jié)點(diǎn)的next值找到新節(jié)點(diǎn)。在第二圈遍歷的時(shí)候，我們可以依次更新復(fù)制節(jié)點(diǎn)的random指針，將其指向新的復(fù)制節(jié)點(diǎn)。最后一圈遍歷，我們調(diào)整next指針，恢復(fù)原鏈表和塑造新鏈表。

    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;
    }

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~