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;
}
}
最近比較忙。之前寫的題目一直沒有更新?，F(xiàn)在正好有點(diǎn)時(shí)間，更新一下。
這道題木之前聽學(xué)長(zhǎng)說過，他在面試微軟的時(shí)候被問到了。
我寫了下，其實(shí)不是很難。
最主要的問題是想清楚怎么copy 一個(gè) linked list.
就是做一個(gè)新的指針，不斷地申請(qǐng)新的內(nèi)存，value就是對(duì)應(yīng)的原結(jié)點(diǎn)的value。
然后留一個(gè)指針指向前面的結(jié)點(diǎn)，然后不斷更新next。
這個(gè)是大多數(shù)人可以做到的。
那么，那個(gè)隨機(jī)指針，random， 怎么辦？
那就是在復(fù)制這個(gè)鏈表的時(shí)候，把原結(jié)點(diǎn)和現(xiàn)結(jié)點(diǎn)放進(jìn)HashMap中。
key: origin pointer -> value: new created pointer
然后根據(jù)原指針的random指向的原鏈表的結(jié)點(diǎn)，找到現(xiàn)鏈表對(duì)應(yīng)的該結(jié)點(diǎn)，更新 現(xiàn)random。
That's it.
又是好多天沒刷題了。
沒想到現(xiàn)在在國(guó)內(nèi)了。刷題還是挺爽的，尤其在學(xué)校機(jī)房。可惜一直沒有大規(guī)模得刷題。
今年跨年。。。然后和女朋友在一塊兒，還得和她爸媽吃飯，就馬上。
人生真是有趣。
Anyway, Good luck, Richardo!
這道題目又是有三種做法。
我自己寫了兩種，第三種感覺很直接簡(jiǎn)潔，看答案的。
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,
思路也沒什么好說的。
這其實(shí)就是 clone graph, 所以一般都需要 一個(gè) hashmap，避免重復(fù)拷貝。
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);
}
}
這個(gè)的話過不了。
stack over flow
的確，當(dāng)輸入的鏈表很大的時(shí)候，就爆棧了。
所以 reverse linked list 的時(shí)候，用iteration做更好。
第三種方法，先把所有的結(jié)點(diǎn)拷貝下，放進(jìn)map中，不考慮連接問題。
然后當(dāng)所有拷貝結(jié)點(diǎn)也都生成好了，開始重新遍歷hashtable，把他們連接起來，很簡(jiǎn)潔，很直接。
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
