Java復雜鏈表的示例分析

這篇文章將為大家詳細講解有關Java復雜鏈表的示例分析，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

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復雜鏈表的示例分析”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。