題目

請實現?copyRandomList?函數，復制一個復雜鏈表。在復雜鏈表中，每個節(jié)點除了有一個?next?指針指向下一個節(jié)點，還有一個?random?指針指向鏈表中的任意節(jié)點或者?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é)點。
• 節(jié)點數目不超過 1000 。

解答

源代碼

/*
// Definition for a Node.
class Node {int val;Node next;Node random;public Node(int val) {this.val = val;this.next = null;this.random = null;}
}
*/
class Solution {Map<Node, Node> map = new HashMap<>();public Node copyRandomList(Node head) {if (head == null) {return null;}if (!map.containsKey(head)) {Node cur = new Node(head.val);map.put(head, cur);cur.next = copyRandomList(head.next);cur.random = copyRandomList(head.random);}return map.get(head);}
}

總結

一開始低估了問題復雜性了，以為遍歷兩次就可以了，一次把節(jié)點、鏈表創(chuàng)建出來，第二次遍歷把random指針也設置好。但是實際操作的時候發(fā)現，第二次遍歷時雖然可以得到原鏈表節(jié)點的random指針指向的節(jié)點，但是復制出來的這個鏈表節(jié)點的random指針應該指向的節(jié)點丟了。

學習了題解，用了回溯算法，方法輸入的是原鏈表的節(jié)點，返回的是復制出來的鏈表的對應節(jié)點。