Java復雜鏈表的復制詳解

Posted on by

1.題目

請實現 copyRandomList 函數，復制一個復雜鏈表。在復雜鏈表中，每個節點除瞭有一個 next 指針指向下一個節點，還有一個 random 指針指向鏈表中的任意節點或者 null。

題目來源：力扣（LeetCode）

鏈接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof

2.解法

2.1 拼接+拆分

首先我們逐個將節點復制並且和原來的鏈表連起來得新鏈表；

然後再構建新鏈表的random 指向。當訪問原節點 cur 的隨機指向節點 cur.random 時，對應新節點 cur.next 的隨機指向節點為 cur.random.next 

將得到的新鏈表之間的復制節點拆分出來連成一個復制鏈表，拆分成原鏈表和復制鏈表。

鏈表圖

 復制節點

 將復制節點的random.next 連接起來

 拆分成兩個鏈表

3.代碼

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) {
            return null;
        }        
        //1.復制各個鏈表，並連接
        Node cur = head;
        while (cur != null) {
            //復制
            Node prev = new Node(cur.val);
            prev.next = cur.next;
            //連接
            cur.next = prev;
            //往後走
            cur = prev.next;
        }
        //2.構建各新節點的random 指向
        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        //3.拆分復制的鏈表
        cur = head.next;
        Node node = head;
        Node nodeNext = head.next;
        while (cur.next != null) {
            node.next = node.next.next;
            cur.next = cur.next.next;
            node = node.next;
            cur = cur.next;
        }
        node.next = null;//尾節點
        return nodeNext;//返回新鏈表的頭結點
    }
}

到此這篇關於Java復雜鏈表的復制詳解的文章就介紹到這瞭,更多相關Java 復雜鏈表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：