CopyListWithRandomPointer [source code]
public class CopyListWithRandomPointer {
static
/******************************************************************************/
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null)
return null;
HashMap<RandomListNode, RandomListNode> map = new HashMap<> ();
RandomListNode cur = head, copy_dummy = new RandomListNode (0), copy_cur = copy_dummy;
while (cur != null) {
copy_cur.next = new RandomListNode (cur.label);
map.put (cur, copy_cur.next);
cur = cur.next;
copy_cur = copy_cur.next;
}
copy_cur = copy_dummy.next;
cur = head;
while (copy_cur != null) {
if (cur.random != null)
copy_cur.random = map.get (cur.random);
cur = cur.next;
copy_cur = copy_cur.next;
}
return copy_dummy.next;
}
}
/******************************************************************************/
public static void main(String[] args) {
CopyListWithRandomPointer.Solution tester = new CopyListWithRandomPointer.Solution();
}
}
刚开始看不懂题目, 就画画看, 你不是觉得没难度吗, 那么你自己手动笨办法trace一个, 看看是不是真的像你想的那么简单;
然后在自己尝试笔算实现的时候, 发现了这个问题的难度: 这个random指针, 不好保存, 因为你copy的时候肯定是用next来遍历, 但是你next走到一个node的时候, 他的random指向的node可能还没有被copy过来;
另外这题没有说过node的value之间不允许有duplicate, 所以单纯先copy之后, 专门再走一遍, 通过lookup node by value来恢复random指针的办法好像也不太行;
能不能直接建立一个从old node到new node之间的1对1的hash mapping?
暂时看不出来问题, 先写;
最后莫名其妙就AC了, 没有看懂这个题目的复杂度在哪里; 不过上面的思考过程还是有指导意义的, 只有自己笔算之后发现难度所在, 才好开始想思路; 没有什么思路是莫名其妙就想到的;
速度是6ms (29%), 应该还有更好的做法, 我这个毕竟是2pass的, 估计还有1pass的做法;
没有editorial;
An intuitive solution is to keep a hash table for each node in the list, via which we just need to iterate the list in 2 rounds respectively to create nodes and assign the values for their random pointers. As a result, the space complexity of this solution is O(N), although with a linear time complexity.
As an optimised solution, we could reduce the space complexity into constant. The idea is to associate the original node with its copy node in a single linked list. In this way, we don’t need extra space to keep track of the new nodes.
The algorithm is composed of the follow three steps which are also 3 iteration rounds.
- Iterate the original list and duplicate each node. The duplicate of each node follows its original immediately.
- Iterate the new list and assign the random pointer for each duplicated node.
- Restore the original list and extract the duplicated nodes.
The algorithm is implemented as follows:
还是挺没有想到的, 居然可以O(1)空间;
public RandomListNode copyRandomList(RandomListNode head) {
RandomListNode iter = head, next;
// First round: make copy of each node,
// and link them together side-by-side in a single list.
while (iter != null) {
next = iter.next;
RandomListNode copy = new RandomListNode(iter.label);
iter.next = copy;
copy.next = next;
iter = next;
}
// Second round: assign random pointers for the copy nodes.
iter = head;
while (iter != null) {
if (iter.random != null) {
iter.next.random = iter.random.next;
}
iter = iter.next.next;
}
// Third round: restore the original list, and extract the copy list.
iter = head;
RandomListNode pseudoHead = new RandomListNode(0);
RandomListNode copy, copyIter = pseudoHead;
while (iter != null) {
next = iter.next.next;
// extract the copy
copy = iter.next;
copyIter.next = copy;
copyIter = copy;
// restore the original list
iter.next = next;
iter = next;
}
return pseudoHead.next;
}
讲到O(1)空间, 实际上就是那么几个方法; 他这里用的方法就是modify input(区分与input flags这种);
最后算法的组成还是很清晰的; 这个想法确实是不错; 我们最后想要做的一个就是, 对于一个node, 我们在他的node.copy的时候, 要能够找到node.random.copy. 直接的做法肯定就是HashMap这种直接的存储结构; 另外一种就是自己设计一个特殊的结构, 让你自己清楚的知道怎么去寻找;
Great solution, but it is not O(1) space, you can argue that no extra data structure is used, but it’s still O(n) space.
这个extra可以稍微讨论一下; 不过output真的要算space开销吗?
Very nice idea! After reading the idea, I wrote it in Python and then compared it to your code. Not surprisingly, it’s very similar, but also a little different.
def copyRandomList(self, head):
# Insert each node's copy right after it, already copy .label
node = head
while node:
copy = RandomListNode(node.label)
copy.next = node.next
node.next = copy
node = copy.next
# Set each copy's .random
node = head
while node:
node.next.random = node.random and node.random.next
node = node.next.next
# Separate the copied list from the original, (re)setting every .next
node = head
copy = head_copy = head and head.next
while node:
node.next = node = copy.next
copy.next = copy = node and node.next
return head_copy
Technically, it is still O(n) space complexity, and this is the min space required. But, it is truly O(1) extra space. good solution.
https://leetcode.com/problems/copy-list-with-random-pointer/discuss/43488/Java-O(n)-solution
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) return null;
Map<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
// loop 1. copy all the nodes
RandomListNode node = head;
while (node != null) {
map.put(node, new RandomListNode(node.label));
node = node.next;
}
// loop 2. assign next and random pointers
node = head;
while (node != null) {
map.get(node).next = map.get(node.next);
map.get(node).random = map.get(node.random);
node = node.next;
}
return map.get(head);
}
先直接所有的copy都丢在一个Map里面, 而不是直接就已经放到这个list里面去了; 这样好像确实方便一点;
In the loop2. assign next and random pointers.
We should check whether iter.next or iter.random is null or not!
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if(head==null){
return null;
}
Hashtable<RandomListNode,RandomListNode> ht= new Hashtable<RandomListNode,RandomListNode>();
RandomListNode iter=head;
while(iter!=null){
ht.put(iter,new RandomListNode(iter.label));
iter=iter.next;
}
iter=head;
while(iter!=null){
if(iter.next!=null){
ht.get(iter).next=ht.get(iter.next);
}
if(iter.random!=null){
ht.get(iter).random=ht.get(iter.random);
}
iter=iter.next;
}
return ht.get(head);
}
}
差不多吧, 不加其实也行; 不对, 如果node.next是Null, 或者node.random是Null, 那么就有一个map.get(null)的操作, 这个有毛病吗?
java> map.get (null)
java.lang.Object res2 = null
好像没有问题;
@ernieho map.get(null) is null, so we can reduce the check
Clean solution, but I have some concerns when I thought about HashTables: What is RandomListNode’s hashValue, is it Object’s in-memory representation? Is it guaranteed to be unique for each object?
For some followup, if the RandomListNode’s a black-box, seems we cannot use this solution, cause its hash value computation is not transparent. Am I correct?
Here's how the 1st algorithm goes.
Consider l1 as a node on the 1st list and l2 as the corresponding node on 2nd list.
Step 1:
Build the 2nd list by creating a new node for each node in 1st list.
While doing so, insert each new node after it's corresponding node in the 1st list.
Step 2:
The new head is the 2nd node as that was the first inserted node.
Step 3:
Fix the random pointers in the 2nd list: (Remember that l1->next is actually l2)
l2->random will be the node in 2nd list that corresponds l1->random,
which is next node of l1->random.
Step 4:
Separate the combined list into 2: Splice out nodes that are part of second list.
Return the new head that we saved in step 2.
RandomListNode *copyRandomList(RandomListNode *head) {
RandomListNode *newHead, *l1, *l2;
if (head == NULL) return NULL;
for (l1 = head; l1 != NULL; l1 = l1->next->next) {
l2 = new RandomListNode(l1->label);
l2->next = l1->next;
l1->next = l2;
}
newHead = head->next;
for (l1 = head; l1 != NULL; l1 = l1->next->next) {
if (l1->random != NULL) l1->next->random = l1->random->next;
}
for (l1 = head; l1 != NULL; l1 = l1->next) {
l2 = l1->next;
l1->next = l2->next;
if (l2->next != NULL) l2->next = l2->next->next;
}
return newHead;
}
就是前面那个方法;
Here's how the 2nd algorithm goes.
Consider l1 as a node on the 1st list and l2 as the corresponding node on 2nd list.
Step 1:
Build the 2nd list by creating a new node for each node in 1st list.
While doing so, set the next pointer of the new node to the random pointer
of the corresponding node in the 1st list. And set the random pointer of the
1st list's node to the newly created node.
Step 2:
The new head is the node pointed to by the random pointer of the 1st list.
Step 3:
Fix the random pointers in the 2nd list: (Remember that l1->random is l2)
l2->random will be the node in 2nd list that corresponds to the node in the
1st list that is pointed to by l2->next,
Step 4:
Restore the random pointers of the 1st list and fix the next pointers of the
2nd list. random pointer of the node in 1st list is the next pointer of the
corresponding node in the 2nd list. This is what we had done in the
1st step and now we are reverting back. next pointer of the node in
2nd list is the random pointer of the node in 1st list that is pointed to
by the next pointer of the corresponding node in the 1st list.
Return the new head that we saved in step 2.
RandomListNode *copyRandomList(RandomListNode *head) {
RandomListNode *newHead, *l1, *l2;
if (head == NULL) return NULL;
for (l1 = head; l1 != NULL; l1 = l1->next) {
l2 = new RandomListNode(l1->label);
l2->next = l1->random;
l1->random = l2;
}
newHead = head->random;
for (l1 = head; l1 != NULL; l1 = l1->next) {
l2 = l1->random;
l2->random = l2->next ? l2->next->random : NULL;
}
for (l1 = head; l1 != NULL; l1 = l1->next) {
l2 = l1->random;
l1->random = l2->next;
l2->next = l1->next ? l1->next->random : NULL;
}
return newHead;
}
这个算法是有点复杂的: 三个阶段, 红色, 紫色, 绿色(只画了第一个);
算法设计的intuition应该是, 合理的利用两个指针本身来进行存储; 本来l1->l1.random是有一个mapping的; 他这里是想到, 当我们在做l2的时候, 实际上是不用急着用l2.next把l2全部都连起来的; 因为l1本身是连起来的, 所以只要保证每一个l1能找到自己的l2, 那么就可以保证l2的node之间的顺序不会乱;
两个想法结合起来, 他就是把原来的l2->l1.random这样一个mapping, 改成了l1->l1.copy->l1.random这样的一个mapping, 这样无论是从了l1到copy, 还是从L1到自己的random, 都可以方便的访问(通过L1->copy->copy.random的中转操作);
这样一个设计的优势就是最后建立了这样一个完全的对应mapping关系, 找l1.random in L1, 只要l1-(random)->l2-(next)->l1.random(in L1);
找l2.random in L2: l2-(next)->l1-(random)->l2.random(in L2);
这个设计总体来说确实还是有点复杂的; 前两步完成之后, L2的random指针全部都是正确的; 现在要修正的是L1的random指针和L2的next指针;
这里设计上有一个巧妙的地方: 你仔细看图, 正式因为是一个从左到右的顺序, 当我们删除L2(1)的next和L1(1)的random的时候, 是可以放心不会出错的, 因为后面的node不重新需要1这个node的指针提供的信息(红色的箭头全部都是不往左边回头的)..不对, 好像讲的不太对;
l1->random = l2->next;
l2->next = l1->next ? l1->next->random : NULL;
这两行;
看到这里, l2->next现在存储的是原来的l1->random, 这个我们是知道的; 你看他这里的操作顺序, 先把l2->next还给l1->random之后, 在对l2->next进行更新; 这样保证不会有信息丢失;
然后在更新l2.next的时候, 用到了l1.next.random, 注意了, 因为l1.next是一个从来都没有修改过的指针, 所以现在通过l1.next.random来寻找l1.next.copy是完全安全的; 这个random指针只有等到下一个iteration才会被修改;
The idea is:
Step 1: create a new node for each existing node and join them together
eg: A->B->C will be A->A’->B->B’->C->C’Step2: copy the random links: for each new node n’, n’.random = n.random.next
Step3: detach the list: basically n.next = n.next.next; n’.next = n’.next.next
Here is the code:
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if(head==null){
return null;
}
RandomListNode n = head;
while (n!=null){
RandomListNode n2 = new RandomListNode(n.label);
RandomListNode tmp = n.next;
n.next = n2;
n2.next = tmp;
n = tmp;
}
n=head;
while(n != null){
RandomListNode n2 = n.next;
if(n.random != null)
n2.random = n.random.next;
else
n2.random = null;
n = n.next.next;
}
//detach list
RandomListNode n2 = head.next;
n = head;
RandomListNode head2 = head.next;
while(n2 != null && n != null){
n.next = n.next.next;
if (n2.next == null){
break;
}
n2.next = n2.next.next;
n2 = n2.next;
n = n.next;
}
return head2;
}
}
2014年就有人想出来这个做法了;
Using a HashMap and there are n recursive calls.
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
HashMap<RandomListNode,RandomListNode> nodemap = new HashMap<RandomListNode,RandomListNode>();
return copyListHelper(head, nodemap);
}
public RandomListNode copyListHelper(RandomListNode head, HashMap<RandomListNode,RandomListNode> nodemap) {
if(head==null) return null;
if(nodemap.containsKey(head)) return nodemap.get(head);
RandomListNode ret = new RandomListNode(head.label);
nodemap.put(head,ret);
ret.next = copyListHelper(head.next, nodemap);
ret.random = copyListHelper(head.random,nodemap);
return ret;
}
解答过程中的一个难点就是, l1的random可能指向自己之前的, 也可能指向自己之后的, 所以当你刚做完l1.copy的时候, 你不知道l1.copy.random这个时候是否可以设置;
他这里直接就设置, 用一个recursion加上memo, 这样可以保证: 假如l1.random还没有copy, 那么就先进行一个copy的操作(返回的就是copy), 假如已经copy过了, 直接memo里面拿出来就行了; 这个思路其实还是不错的;
submission: 2(68):
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if(head==null)
return null;
getNext(head);
getRandom(head);
return split(head);
}
public void getNext(RandomListNode head){
while(head!=null){
RandomListNode newhead=new RandomListNode(head.label);
newhead.random=head.random;
newhead.next=head.next;
head.next=newhead;
head=head.next.next;
}
return;
}
public void getRandom(RandomListNode head){
while(head!=null){
if(head.next.random!=null)
head.next.random=head.random.next;
head=head.next.next;
}
return;
}
public RandomListNode split(RandomListNode head){
RandomListNode newhead=head.next;
while(head!=null){
RandomListNode temp=head.next;
head.next=temp.next;
head=head.next;
if(temp.next!=null)
temp.next=temp.next.next;
}
return newhead;
}
}
大概看了一下, 好像就是那个InPlace的做法.
Problem Description
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
Difficulty:Medium
Total Accepted:147.8K
Total Submissions:570.6K
Contributor:LeetCode
Companies
microsoftamazonbloomberguber
Related Topics
hash tablelinked list
Similar Questions
Clone Graph