Massive Algorithms: LeetCode 138 - Copy List with Random Pointer

LeetCode 138 - Copy List with Random Pointer

https://leetcode.com/problems/copy-list-with-random-pointer/

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.

Example 1:

Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

Note:

You must return the copy of the given head as a reference to the cloned list.

X. https://leetcode.com/problems/copy-list-with-random-pointer/discuss/43491/A-solution-with-constant-space-complexity-O(1)-and-linear-time-complexity-O(N)

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.

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;
}

X. 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);
}

https://leetcode.com/problems/copy-list-with-random-pointer/discuss/43497/2-clean-C%2B%2B-algorithms-without-using-extra-arrayhash-table.-Algorithms-are-explained-step-by-step.
Clone a linked list with next and random pointer | Set 2 - GeeksforGeeks
You are given a Double Link List with one pointer of each node pointing to the next node just like in a single link list. The second pointer however CAN point to any node in the list and not just the previous node. Now write a program in O(n) time to duplicate this list. That is, write a program which will create a copy of this list.
ArbitLinked List1

Method 1 (Uses O(n) extra space)
This method stores the next and arbitrary mappings (of original list) in an array first, then modifies the original Linked List (to create copy), creates a copy. And finally restores the original list.

1. Traverse the original linked list and make a copy in terms of data.

2. Make a hash map of key value pair with original linked list node and copied linked list node.

3. Traverse the original linked list again and using the hash map adjust the next and random reference of cloned linked list nodes.

    public LinkedList clone()

{

        // Initialize two references, one with original

        // list's head.

        Node origCurr = this.head, cloneCurr = null;

        // Hash map which contains node to node mapping of

        // original and clone linked list.

        Map<Node, Node> map = new HashMap<Node, Node>();

        // Traverse the original list and make a copy of that

        // in the clone linked list.

        while (origCurr != null)

{

            cloneCurr = new Node(origCurr.data);

            map.put(origCurr, cloneCurr);

            origCurr = origCurr.next;

}

        // Adjusting the original list reference again.

        origCurr = this.head;

        // Traversal of original list again to adjust the next

        // and random references of clone list using hash map.

        while (origCurr != null)

{

            cloneCurr = map.get(origCurr);

            cloneCurr.next = map.get(origCurr.next);

            cloneCurr.random = map.get(origCurr.random);

            origCurr = origCurr.next;

}

        //return the head reference of the clone list.

        return new LinkedList(map.get(this.head));

}

Java code: http://xixiaogualu.blogspot.com/2013/10/leetcode-copy-list-with-random-pointer.html


public RandomListNode copyRandomList(RandomListNode head) {


if(head==null) return null;


HashMap<RandomListNode,RandomListNode> hm=new HashMap<RandomListNode,RandomListNode>();


RandomListNode p=head;


while(p!=null){


RandomListNode n=new RandomListNode(p.label);


hm.put(p,n);


p=p.next;


}


p=head;


while(p!=null){


RandomListNode n=hm.get(p);


n.next=null;n.random=null; // null check.


if(p.next!=null)


n.next=hm.get(p.next);


if(p.random!=null)


n.random=hm.get(p.random);


p=p.next;


}


return hm.get(head);


}

http://blog.csdn.net/linhuanmars/article/details/22463599
Don't have to create newHead first.
http://www.programcreek.com/2012/12/leetcode-copy-list-with-random-pointer/
Difference: create next pointer when add to hashmap, code is more complex and error prone than pervious version.

public RandomListNode copyRandomList(RandomListNode head) {
 if (head == null)
  return null;
 HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
 RandomListNode newHead = new RandomListNode(head.label);
 
 RandomListNode p = head;
 RandomListNode q = newHead;
 map.put(head, newHead);
 
 p = p.next;
 while (p != null) {
  RandomListNode temp = new RandomListNode(p.label);
  map.put(p, temp);
  q.next = temp;
  q = temp;
  p = p.next;
 }
 
 p = head;
 q = newHead;
 while (p != null) {
  if (p.random != null)
   q.random = map.get(p.random);
  else
   q.random = null;
 
  p = p.next;
  q = q.next;
 }
 
 return newHead;
}

Using Hashmap but only traverse once
http://www.jiuzhang.com/solutions/copy-list-with-random-pointer/

    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }

        HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        RandomListNode dummy = new RandomListNode(0);
        RandomListNode pre = dummy, newNode;
        while (head != null) {
            if (map.containsKey(head)) {
                newNode = map.get(head);
            } else {
                newNode = new RandomListNode(head.label);
                map.put(head, newNode);
            }
            pre.next = newNode;

            if (head.random != null) {
                if (map.containsKey(head.random)) {
                    newNode.random = map.get(head.random);
                } else {
                    newNode.random = new RandomListNode(head.random.label);
                    map.put(head.random, newNode.random);
                }
            }

            pre = newNode;
            head = head.next;
        }

        return dummy.next;
    }

Constant Space: don't use hashmap.
http://shmilyaw-hotmail-com.iteye.com/blog/2166535
1. 遍历原有链表，在每个原来的节点后面增加一个拷贝节点。
2. 根据原节点的随机指针设置拷贝节点的随机指针。
3. 剥离出所有拷贝节点。

During interview, it's better to extract logic into different methods, so we can first write the main logic, easier to write code in the whiteboard.

    private void copyNext(RandomListNode head) {
        while (head != null) {
            RandomListNode newNode = new RandomListNode(head.label);
            newNode.random = head.random;
            newNode.next = head.next;
            head.next = newNode;
            head = head.next.next;
        }
    }

    private void copyRandom(RandomListNode head) {
        while (head != null) {
            if (head.next.random != null) {
                head.next.random = head.random.next;
            }
            head = head.next.next;
        }
    }
    private RandomListNode splitList(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;
    }
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }
        copyNext(head);
        copyRandom(head);
        return splitList(head);
    }

http://blog.csdn.net/pengyan0812/article/details/46423067

Linklist * createComplexLinklist(int n)
{
Linklist * head = (Linklist *)malloc(sizeof(Linklist)); // 链表的头结点
head -> data = 0; // 将头结点的数据域赋值为0，head既当头结点，又当NULL
head -> next = NULL;
Linklist * p = head; // p指针指向链表的最后一个结点
Linklist * s = NULL; // 新构造的链表结点
int i;
int data;
int Ti; // 表示链表结点的另一个指针的指向
// 构造链表结点的值和指向下一个结点的指针
for(i = 1;i <= n;i++)
{
scanf("%d",&data);
s = (Linklist *)malloc(sizeof(Linklist));
s -> data = data;
s -> next = p -> next;
p -> next = s; // 将s结点插入到链表末尾
p = s; // p始终指向当前链表的最后一个结点
LinkNodeAddress[i] = s; // 将s结点的地址保存到链表结点地址数组中
}
// 构造链表结点的特殊指针值
p = head -> next;
for(i = 1;i <= n;i++)
{
scanf("%d",&Ti);
if(0 != Ti)
{
p -> specialPoint = LinkNodeAddress[Ti];
}
else
{
p -> specialPoint = head; // 如果Ti == 0，则将特殊指针指向头结点(此时头结点等价于NULL)
}
p = p -> next;
}
return head;
}

Read full article from Clone a linked list with next and random pointer | Set 2 - GeeksforGeeks

LeetCode 138 - Copy List with Random Pointer

Labels

Popular Posts