題?描述

輸??個復雜鏈表（每個節(jié)點中有節(jié)點值，以及兩個指針，?個指向下?個節(jié)點，另?個特殊指針random 指向?個隨機節(jié)點），請對此鏈表進?深拷?，并返回拷?后的頭結點。（注意，輸出結果中請不要返回參數中的節(jié)點引?，否則判題程序會直接返回空）

思路及解答

哈希表映射

使用哈希表存儲原節(jié)點和新節(jié)點的映射關系：

1. 第一次遍歷：創(chuàng)建所有新節(jié)點，并建立原節(jié)點到新節(jié)點的映射
2. 第二次遍歷：根據映射關系設置新節(jié)點的next和random指針

public class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        
        // 創(chuàng)建哈希表存儲原節(jié)點到新節(jié)點的映射
        HashMap<Node, Node> map = new HashMap<>();
        Node current = head;
        
        // 第一次遍歷：創(chuàng)建所有新節(jié)點并建立映射
        while (current != null) {
            map.put(current, new Node(current.val));
            current = current.next;
        }
        
        // 第二次遍歷：設置新節(jié)點的next和random指針
        current = head;
        while (current != null) {
            Node newNode = map.get(current);
            newNode.next = map.get(current.next);
            newNode.random = map.get(current.random);
            current = current.next;
        }
        
        return map.get(head);
    }
}

class Node {
    int val;
    Node next;
    Node random;
    
    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

• ?時間復雜度?：O(n)，兩次遍歷鏈表
• ?空間復雜度?：O(n)，需要存儲所有節(jié)點的映射關系

節(jié)點插入拆分法

通過在原鏈表中插入新節(jié)點來避免使用額外空間：

1. ?節(jié)點復制插入?：在每個原節(jié)點后面插入一個復制的新節(jié)點
2. ?設置random指針?：新節(jié)點的random指向原節(jié)點random的下一個節(jié)點
3. ?鏈表拆分?：將混合鏈表拆分為原鏈表和新鏈表

public class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        
        // 第一步：在每個節(jié)點后面插入復制的節(jié)點
        Node current = head;
        while (current != null) {
            Node newNode = new Node(current.val);
            newNode.next = current.next;
            current.next = newNode;
            current = newNode.next;
        }
        
        // 第二步：設置復制節(jié)點的random指針
        current = head;
        while (current != null) {
            if (current.random != null) {
                current.next.random = current.random.next;
            }
            current = current.next.next;
        }
        
        // 第三步：拆分鏈表
        Node newHead = head.next;
        current = head;
        while (current != null) {
            Node temp = current.next;
            current.next = temp.next;
            if (temp.next != null) {
                temp.next = temp.next.next;
            }
            current = current.next;
        }
        
        return newHead;
    }
}

• ?時間復雜度?：O(n)，三次遍歷鏈表
• ?空間復雜度?：O(1)，只使用固定數量的指針變量