Copy List with Random Pointer 105

Question

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.

Challenge

Could you solve it with O(1) space?

Solution

问题不难。trick的地方在于在复制一个点时，其random应该指向的点还没有被创建，因此无法指向该点。

可以先用HashMap保存所有原始点和其复制点。然后逐点复制next和random关系。

也可以将每个点和其复制点相连，变成以下形式：

head->head'->node1->node1'->...

1) 原始点与复制点相连，复制点指向对应原始点的random

2) 调整复制点的random指向原始点random的下一个点（即复制的random点）

3) 拆分原始点和复制点的链表

代码如下：

HashMap:

public class Solution {
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
    **/

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

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

        RandomListNode dummy = new RandomListNode(0);
        dummy.next = head;

        while(head != null){
            myMap.put(head, new RandomListNode(head.label));
            head = head.next;
        }

        head = dummy.next;
        RandomListNode newHead = new RandomListNode(0);
        newHead.next = myMap.get(head);
        while(head != null){
            myMap.get(head).next = myMap.get(head.next);
            myMap.get(head).random = myMap.get(head.random);
            head = head.next;
        }

        return newHead.next;*/
    }
}

Duplicate:

public class Solution {
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
    **/

    public RandomListNode copyRandomList(RandomListNode head) {
        //先构建node1->node1'->node2->node2'->...，再拆分
    private void copyNext(RandomListNode head){
        while(head != null){
            RandomListNode newNode = new RandomListNode(head.label);
            //先把复制点的random指向head的random
            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){
                //将复制点的random指向head的random之后一个点（为head的random的复制点）
                head.next.random = head.random.next;
            }
            head = head.next.next;
        }
    }
    //将list拆为原list和复制的list
    private RandomListNode split(RandomListNode head){
        RandomListNode newHead = new RandomListNode(0);
        newHead.next = head.next;
        while(head != null){
            RandomListNode temp = head.next;
            head.next = temp.next;
            if(temp.next != null){
                temp.next = temp.next.next;
            }
            head = head.next;
        }
        return newHead.next;
    }

    public RandomListNode copyRandomList(RandomListNode head) {
        // write your code here
        if(head == null){
            return head;
        }

        copyNext(head);
        copyRandom(head);

        return split(head);
    }
}