๐ ๅๆ Offer 35. ๅคๆ้พ่กจ็ๅคๅถ
2022ๅนด10ๆ10ๆฅ
- algorithm
๐ ๅๆ Offer 35. ๅคๆ้พ่กจ็ๅคๅถ
้พๅบฆ: ๐
้ฎ้ขๆ่ฟฐ
่งฃๆณ
/*
// 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 {
public Node copyRandomList(Node head) {
// ๆ่ทฏ๏ผ
// HashMap ๅญๅจ ๅ่็น - ๆฐ่็น
if(head == null) {
return null;
}
HashMap<Node, Node> map = new HashMap<>();
Node res = new Node(-1);
Node pre = res;
Node cur = head;
while(cur != null) {
Node node = new Node(cur.val); // ๆฐๅคๅถ่็น
map.put(cur, node);
pre.next = node;
pre = node;
cur = cur.next;
}
// ๅกซๅ
rand ่็น
cur = head;
while(cur != null) {
if(cur.random != null) {
Node origRand = cur.random;
Node node = map.get(cur);
Node rand = map.get(origRand);
node.random = rand;
// System.out.println(cur.val + " " + origRand.val + " " + node.val + " " + rand.val);
}
cur = cur.next;
}
return res.next;
}
}