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;
}
}
最近比较忙。之前写的题目一直没有更新。现在正好有点时间，更新一下。
这道题木之前听学长说过，他在面试微软的时候被问到了。
我写了下，其实不是很难。
最主要的问题是想清楚怎么copy 一个 linked list.
就是做一个新的指针，不断地申请新的内存，value就是对应的原结点的value。
然后留一个指针指向前面的结点，然后不断更新next。
这个是大多数人可以做到的。
那么，那个随机指针，random， 怎么办？
那就是在复制这个链表的时候，把原结点和现结点放进HashMap中。
key: origin pointer -> value: new created pointer
然后根据原指针的random指向的原链表的结点，找到现链表对应的该结点，更新 现random。
That's it.
又是好多天没刷题了。
没想到现在在国内了。刷题还是挺爽的，尤其在学校机房。可惜一直没有大规模得刷题。
今年跨年。。。然后和女朋友在一块儿，还得和她爸妈吃饭，就马上。
人生真是有趣。
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做更好。
第三种方法，先把所有的结点拷贝下，放进map中，不考虑连接问题。
然后当所有拷贝结点也都生成好了，开始重新遍历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
