本題考察的是鏈表的插入刪除操作

題目描述

給定一個(gè)鏈表，每個(gè)節(jié)點(diǎn)包含一個(gè)額外增加的隨機(jī)指針，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)。
要求返回這個(gè)鏈表的深度拷貝。

鏈表的結(jié)點(diǎn)結(jié)構(gòu)如下

 class RandomListNode {
     int label;
     RandomListNode next, random;
     RandomListNode(int x) { this.label = x; }
 };
 

題目思考

這道題比常規(guī)的鏈表復(fù)制多了一個(gè)隨機(jī)指針random。按照常規(guī)的解法，我們可以用一個(gè)HashMap<RandomListNode ,RandomListNode >維護(hù)從原始結(jié)點(diǎn)到復(fù)制結(jié)點(diǎn)的映射，這樣我們?cè)趶?fù)制鏈表的時(shí)候不會(huì)重復(fù)創(chuàng)建結(jié)點(diǎn)。
但是，在看了大神的代碼后，我驚呆了，原來還可以這么做。詳細(xì)解析往下看

代碼1

java 7ms

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head==null)
            return null;
        Map<RandomListNode,RandomListNode> map=new HashMap<RandomListNode,RandomListNode>();   //創(chuàng)建從源結(jié)點(diǎn)到復(fù)制結(jié)點(diǎn)的映射
        RandomListNode myHead = new RandomListNode(head.label),cur=head,myCur=myHead;
        map.put(cur,myCur);//先把頭結(jié)點(diǎn)放到map中
        while(cur!=null){  //首先不管random指針，只按照next指針復(fù)制鏈表，把每一組映射添加到map中
            myCur.next=map.get(cur.next);
            if(myCur.next==null&&cur.next!=null){
                myCur.next=new RandomListNode(cur.next.label);
                map.put(cur.next,myCur.next);
            }
            myCur=myCur.next;
            cur=cur.next;
        }
        cur=head;
        myCur=myHead;
        while(cur!=null){ //連接random指針，把每一組映射添加到map中
            myCur.random=map.get(cur.random);
            if(myCur.random==null&&cur.random!=null){
                myCur.random=new RandomListNode(cur.random.label);
                map.put(cur.random,myCur.random);
            }
            myCur=myCur.next;
            cur=cur.next;
        }
        return myHead;
    }
}

這個(gè)代碼思路很直觀，首先根據(jù)next指針復(fù)制所有結(jié)點(diǎn)，練成一條鏈，并把源結(jié)點(diǎn)作為key,復(fù)制后的結(jié)點(diǎn)作為value放到map中。然后再連接所有的random指針，根據(jù)源結(jié)點(diǎn)從map中找到復(fù)制后的結(jié)點(diǎn)添加到map指針中。
下面是我復(fù)制大神的代碼

代碼2

java 1ms

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head==null)
            return null;
        RandomListNode cur=head;
        while(cur!=null){
            RandomListNode temp=new RandomListNode(cur.label);  //復(fù)制結(jié)點(diǎn)
            temp.next=cur.next;//把復(fù)制后的結(jié)點(diǎn)放到源結(jié)點(diǎn)的next指針上
            cur.next=temp;
            cur=cur.next.next;
        }
        cur=head;
        while(cur!=null){  //連接所有復(fù)制后結(jié)點(diǎn)的random指針
            cur.next.random= cur.random==null? null:cur.random.next;
            cur=cur.next.next;
        }
        cur=head;
        RandomListNode myHead=cur.next;
        RandomListNode myCur=myHead;
        while(cur!=null){  //刪除源結(jié)點(diǎn)和復(fù)制后結(jié)點(diǎn)之間的連接
            cur.next=myCur.next;
            cur=cur.next;
            myCur.next=cur==null? null:cur.next;
            myCur=myCur.next;
        }
        return myHead;
    }
}

用圖來解釋一下

首先我們把結(jié)點(diǎn)表示成這樣

結(jié)點(diǎn)表示

然后我們假設(shè)需要復(fù)制的鏈表是這樣的

需要復(fù)制的鏈表

首先我們復(fù)制結(jié)點(diǎn)，并把復(fù)制后的結(jié)點(diǎn)放到源結(jié)點(diǎn)的next指針上

復(fù)制結(jié)點(diǎn)，連接next指針

然后連接復(fù)制后結(jié)點(diǎn)的random指針

連接random指針

最后斷開源結(jié)點(diǎn)和復(fù)制后結(jié)點(diǎn)的連接，連接復(fù)制后結(jié)點(diǎn)的next指針

重連random

這樣就完成了鏈表的復(fù)制