My code:
/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
* int label;
* RandomListNode next, random;
* RandomListNode(int x) { this.label = x; }
* };
*/
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null)
return null;
HashMap<RandomListNode, RandomListNode> tracker = new HashMap<RandomListNode, RandomListNode>();
RandomListNode newHead = new RandomListNode(head.label);
tracker.put(head, newHead);
RandomListNode next = head.next;
RandomListNode newNext = newHead;
/** copy the whole linked list with next pointer */
while (next != null) {
newNext.next = new RandomListNode(next.label);
newNext = newNext.next;
tracker.put(next, newNext);
next = next.next;
}
next = head;
newNext = newHead;
while (next != null) {
newNext.random = tracker.get(next.random);
next = next.next;
newNext = newNext.next;
}
return newHead;
}
}
最近比較忙缰犁。之前寫的題目一直沒有更新。現(xiàn)在正好有點時間怖糊，更新一下帅容。
這道題木之前聽學長說過，他在面試微軟的時候被問到了伍伤。
我寫了下并徘，其實不是很難。
最主要的問題是想清楚怎么copy 一個 linked list.
就是做一個新的指針扰魂，不斷地申請新的內(nèi)存麦乞，value就是對應的原結(jié)點的value。
然后留一個指針指向前面的結(jié)點劝评，然后不斷更新next姐直。
這個是大多數(shù)人可以做到的。
那么蒋畜，那個隨機指針声畏，random， 怎么辦姻成？
那就是在復制這個鏈表的時候插龄，把原結(jié)點和現(xiàn)結(jié)點放進HashMap中愿棋。
key: origin pointer -> value: new created pointer
然后根據(jù)原指針的random指向的原鏈表的結(jié)點，找到現(xiàn)鏈表對應的該結(jié)點辫狼，更新 現(xiàn)random初斑。
That's it.
又是好多天沒刷題了。
沒想到現(xiàn)在在國內(nèi)了膨处。刷題還是挺爽的见秤，尤其在學校機房≌娲唬可惜一直沒有大規(guī)模得刷題鹃答。
今年跨年。突硝。测摔。然后和女朋友在一塊兒，還得和她爸媽吃飯解恰，就馬上锋八。
人生真是有趣。
Anyway, Good luck, Richardo!
這道題目又是有三種做法护盈。
我自己寫了兩種挟纱，第三種感覺很直接簡潔，看答案的腐宋。
iteration:
My code:
/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
* int label;
* RandomListNode next, random;
* RandomListNode(int x) { this.label = x; }
* };
*/
public class Solution {
HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) {
return null;
}
RandomListNode dummy = new RandomListNode(-1);
RandomListNode dummym = new RandomListNode(-1);
dummy.next = head;
RandomListNode curr = dummy;
RandomListNode currm = dummym;
while (curr.next != null) {
RandomListNode next = curr.next;
RandomListNode nextm = null;
if (map.containsKey(next)) {
nextm = map.get(next);
}
else {
nextm = clone(next);
map.put(next, nextm);
}
if (next.random != null) {
RandomListNode randomm = null;
if (map.containsKey(next.random)) {
randomm = map.get(next.random);
}
else {
randomm = clone(next.random);
map.put(next.random, randomm);
}
nextm.random = randomm;
}
currm.next = nextm;
currm = nextm;
curr = curr.next;
}
return dummym.next;
}
private RandomListNode clone(RandomListNode node) {
return new RandomListNode(node.label);
}
}
AC,
思路也沒什么好說的紊服。
這其實就是 clone graph, 所以一般都需要 一個 hashmap，避免重復拷貝胸竞。
recursion:
My code:
/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
* int label;
* RandomListNode next, random;
* RandomListNode(int x) { this.label = x; }
* };
*/
public class Solution {
HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) {
return null;
}
RandomListNode headm = null;
if (map.containsKey(head)) {
headm = map.get(head);
}
else {
headm = clone(head);
map.put(head, headm);
}
if (head.random != null) {
RandomListNode random = null;
if (map.containsKey(head.random)) {
random = map.get(head.random);
}
else {
random = clone(head.random);
map.put(head.random, random);
}
headm.random = random;
}
headm.next = copyRandomList(head.next);
return headm;
}
private RandomListNode clone(RandomListNode node) {
return new RandomListNode(node.label);
}
}
這個的話過不了欺嗤。
stack over flow
的確，當輸入的鏈表很大的時候卫枝，就爆棧了煎饼。
所以 reverse linked list 的時候，用iteration做更好校赤。
第三種方法腺占，先把所有的結(jié)點拷貝下，放進map中痒谴，不考慮連接問題。
然后當所有拷貝結(jié)點也都生成好了铡羡，開始重新遍歷hashtable积蔚，把他們連接起來，很簡潔烦周，很直接尽爆。
My code:
/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
* int label;
* RandomListNode next, random;
* RandomListNode(int x) { this.label = x; }
* };
*/
public class Solution {
HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) {
return null;
}
RandomListNode curr = head;
while (curr != null) {
map.put(curr, clone(curr));
curr = curr.next;
}
for (Map.Entry<RandomListNode, RandomListNode> entry : map.entrySet()) {
RandomListNode newNode = entry.getValue();
newNode.next = map.get(entry.getKey().next);
newNode.random = map.get(entry.getKey().random);
}
return map.get(head);
}
private RandomListNode clone(RandomListNode node) {
return new RandomListNode(node.label);
}
}
reference:
https://discuss.leetcode.com/topic/29358/very-short-java-solution-with-map
Anyway, Good luck, Richardo! -- 09/09/2016
