建站快車打電話百度云鏈接
題目
請實現?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é)點。