摘要：給定一個鏈表，每個節(jié)點包含一個額外增加的隨機指針，該指針可以指向鏈表中的任何節(jié)點或空節(jié)點。要求返回這個鏈表的深拷貝。提示你必須返回給定頭的拷貝作為對克隆列表的引用。確定隨機節(jié)點的關(guān)系之后再拆分鏈表。其時間復(fù)雜度為，空間復(fù)雜度為。

給定一個鏈表，每個節(jié)點包含一個額外增加的隨機指針，該指針可以指向鏈表中的任何節(jié)點或空節(jié)點。

要求返回這個鏈表的深拷貝。

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

示例：

輸入：
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

解釋：
節(jié)點 1 的值是 1，它的下一個指針和隨機指針都指向節(jié)點 2 。
節(jié)點 2 的值是 2，它的下一個指針指向 null，隨機指針指向它自己。

提示：

你必須返回給定頭的拷貝作為對克隆列表的引用。

Note:

You must return the copy of the given head as a reference to the cloned list.

由于需要考慮隨機指針，隨機指針指向的節(jié)點可能是null，也可能是鏈表的最后一個節(jié)點，深拷貝下，你不能將新鏈表的隨機指針指向原鏈表的節(jié)點，所以無法一遍得到新鏈表。

兩種解題方法，一種是拷貝所有節(jié)點，暫存在一種數(shù)據(jù)結(jié)構(gòu)內(nèi)，然后再遍歷一遍該數(shù)據(jù)結(jié)構(gòu)，找到拷貝的節(jié)點，確定隨機指針的指向。因為每個節(jié)點都要找到隨機指針指向的節(jié)點，如果借助 散列表(字典) 其查找復(fù)雜度為 O(1) ，這樣可以把總時間復(fù)雜度降到 O(n) ，由于要暫存所有節(jié)點，其空間復(fù)雜度為 O(n)。

另一種解題方法是需要三次遍歷得到結(jié)果，簡單來說就是先把每個節(jié)點拷貝，并把拷貝節(jié)點連接到原節(jié)點后面，依次類推。確定隨機節(jié)點的關(guān)系之后再拆分鏈表。是一種很巧妙的思路：

原鏈表：1->2->3
復(fù)制每個節(jié)點到原節(jié)點后面：1->1->2->2->3->3
復(fù)制隨機指針的指向關(guān)系
拆分鏈表：1->2->3, 1->2->3

復(fù)制隨機指針指向時，原節(jié)點的隨機節(jié)點下一個節(jié)點即為新節(jié)點的隨機節(jié)點。假如原鏈表：1->2->3，節(jié)點1的隨機節(jié)點為3，復(fù)制節(jié)點之后：1->1->2->2->3->3

我們只需將新節(jié)點（原節(jié)點1的后一個節(jié)點1）指向原節(jié)點的隨機節(jié)點的后一個節(jié)點（原節(jié)點的隨機節(jié)點為3，而復(fù)制之后隨機節(jié)點3的后一個節(jié)點依然為3，但這個節(jié)點為新節(jié)點），最后拆分鏈表（鏈表拆分不影響節(jié)點指向關(guān)系）。其時間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(1)。

Java：

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        HashMap map = new HashMap<>();//借助hashMap
        Node newHead = new Node(0);//虛擬頭節(jié)點
        Node cur = newHead;//指針指向當(dāng)前節(jié)點
        Node tmp;
        while (head != null) {
            if (map.containsKey(head)) {//查詢原節(jié)點是否已存在于map
                tmp = map.get(head);//如果存在直接取value值
            } else {
                tmp = new Node(head.val);//不存在則新建一個值相同的節(jié)點
                map.put(head, tmp);//存入map，key為原節(jié)點，value為新節(jié)點
            }
            cur.next = tmp;
            if (head.random != null) {//原節(jié)點的隨機節(jié)點不為空的情況下
                if (map.containsKey(head.random)) {//查詢該隨即節(jié)點是否已存在于map
                    tmp.random = map.get(head.random);//存在則直接將新節(jié)點的隨機指針指向其value值
                } else {
                    tmp.random = new Node(head.random.val);//不存在則新建一個值相同的隨機節(jié)點
                    map.put(head.random, tmp.random);//存入map，key為原節(jié)點的隨機節(jié)點，value為新節(jié)點的隨機節(jié)點
                }
            }
            head = head.next;//刷新原鏈表當(dāng)前頭節(jié)點
            cur = tmp;//即cur=cur.next，刷新新鏈表當(dāng)前節(jié)點
        }
        return newHead.next;
    }
}

Python3：

class Solution:
    def copyRandomList(self, head: "Node") -> "Node":
        if not head: return None
        map = {}
        newHead = Node(val=0, next=None, random=None)
        cur = newHead
        while head:
            if head in map.keys():
                tmp = map.get(head)
            else:
                tmp = Node(val=head.val, next=None, random=None)
                map.setdefault(head, tmp)
            cur.next = tmp
            if head.random:
                if head.random in map.keys():
                    tmp.random = map.get(head.random)
                else:
                    tmp.random = Node(val=head.random.val, next=None, random=None)
                    map.setdefault(head.random, tmp.random)
            head = head.next
            cur = tmp
        return newHead.next

Java：

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        //復(fù)制節(jié)點 1->2->3 ==> 1->1->1->2->2->3->3
        Node cur = head;
        while (cur != null) {
            Node next = cur.next;
            Node tmp = new Node(cur.val);
            cur.next = tmp;
            tmp.next = next;
            cur = next;
        }
        //復(fù)制隨機指針
        cur = head;
        while (cur != null) {
            //cur.next.random=>新節(jié)點的隨機節(jié)點     cur.random.next=>原節(jié)點的隨機節(jié)點的下一個節(jié)點
            cur.next.random = cur.random == null ? null : cur.random.next;
            cur = cur.next.next;//鏈表擴展一倍后肯定是偶數(shù)位鏈表，所以可以直接用cur.next.next
        }
        //分離節(jié)點
        cur = head;
        Node newHead = head.next;//新鏈表頭節(jié)點
        while (cur != null) {
            Node tmp = cur.next;
            cur.next = tmp.next;
            cur = cur.next;
            tmp.next = cur == null ? null : cur.next;
        }
        return newHead;
    }
}

Python3：

class Solution:
    def copyRandomList(self, head: "Node") -> "Node":
        if not head: return None
        cur = head
        while cur:
            next = cur.next
            tmp = Node(val=cur.val, next=next, random=None)
            cur.next = tmp
            cur = next
        cur = head
        while cur:
            cur.next.random = cur.random.next if cur.random else None
            cur = cur.next.next
        cur = head
        newHead = head.next
        while cur:
            tmp = cur.next
            cur.next = tmp.next
            cur = cur.next
            tmp.next = cur.next if cur else None
        return newHead

歡迎關(guān)注微.信公.眾號一起學(xué)習(xí)：愛寫B(tài)ug