題目

請(qǐng)實(shí)現(xiàn)?copyRandomList?函數(shù)，復(fù)制一個(gè)復(fù)雜鏈表。在復(fù)雜鏈表中，每個(gè)節(jié)點(diǎn)除了有一個(gè)?next?指針指向下一個(gè)節(jié)點(diǎn)，還有一個(gè)?random?指針指向鏈表中的任意節(jié)點(diǎn)或者?null。

示例 1：

輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

輸入：head = [[1,1],[2,1]]
輸出：[[1,1],[2,1]]

示例 3：

輸入：head = [[3,null],[3,0],[3,null]]
輸出：[[3,null],[3,0],[3,null]]

示例 4：

輸入：head = []
輸出：[]
解釋：給定的鏈表為空（空指針），因此返回 null。

提示：

• -10000 <= Node.val <= 10000
• Node.random?為空（null）或指向鏈表中的節(jié)點(diǎn)。
• 節(jié)點(diǎn)數(shù)目不超過 1000 。

解題思路

1.題目要求我們復(fù)制一個(gè)復(fù)雜鏈表。在這個(gè)復(fù)雜鏈表中，每個(gè)節(jié)點(diǎn)除了有一個(gè)?next?指針指向下一個(gè)節(jié)點(diǎn)，還有一個(gè)?random?指針指向鏈表中的任意節(jié)點(diǎn)或者?null。我們可以用Map來實(shí)現(xiàn)，詳情請(qǐng)查看【138.復(fù)制帶隨機(jī)指針的鏈表】，我們今天用另一種方法去實(shí)現(xiàn)。

2.舉個(gè)例子大家更容易理解

假如所給鏈表如上圖所示，首先我們要做的就是設(shè)置一個(gè) cur 節(jié)點(diǎn)去遍歷鏈表，在遍歷的同時(shí)將所有的節(jié)點(diǎn)復(fù)制一份，復(fù)制出來的每個(gè)節(jié)點(diǎn)都跟在原來節(jié)點(diǎn)的后面。如下圖所示。

?節(jié)點(diǎn)復(fù)制完后我們會(huì)發(fā)現(xiàn)，復(fù)制出來的節(jié)點(diǎn)random指針都為空，那么我們要做的就是要讀取出原節(jié)點(diǎn)的random指針的值，并且將它的后一個(gè)節(jié)點(diǎn)賦給復(fù)制出來的新節(jié)點(diǎn)的random(之所以是后一個(gè)節(jié)點(diǎn)是因?yàn)?，后一個(gè)節(jié)點(diǎn)才是我們的復(fù)制品)。

最后我們要做的工作就是將兩個(gè)鏈表拆分開來，也就是讓 3 的 next 不再指向 3‘ 而是指向 5，讓 3’ 的 next 重新指向 5‘，最后拆分完的結(jié)果如下圖所示。

?這樣我們就得到了原鏈表的復(fù)印件，我們?cè)趶?fù)制鏈表和拆分鏈表的時(shí)候要注意空指針?，所以需要判斷一下。

代碼實(shí)現(xiàn)

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
            return null;
        }
        //復(fù)制鏈表的節(jié)點(diǎn)
        Node cur = head;
        while(cur != null){
            Node next = cur.next;
            cur.next = new Node(cur.val);
            cur.next.next = next; 
            cur = next;
        }
        //復(fù)制隨機(jī)節(jié)點(diǎn)
        cur = head;
        while(cur != null){
            Node nextNode = cur.next;
            nextNode.random = cur.random == null ? null : cur.random.next;
            cur = cur.next.next;

        }
        //拆分鏈表
        Node newHead = head.next;
        cur = head;
        Node curHead = head.next;
        while(cur != null){
            cur.next = cur.next.next;
            cur = cur.next;
            curHead.next = cur == null ? null : cur.next;
            curHead = curHead.next;
        
        }
        return newHead;
    }
}

測試結(jié)果

?文章來源地址http://www.zghlxwxcb.cn/news/detail-671033.html

到了這里，關(guān)于Leetcode-每日一題【劍指 Offer 35. 復(fù)雜鏈表的復(fù)制】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！