[LintCode] 105 Copy List with Random Pointer 解题报告

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.


Challenge
Could you solve it with O(1) space?


思路
1：遍历一遍，每一个节点后面插入一个复制的节点，不考虑random pinter。
a -> b -> c -> null 变成 a -> a -> b -> b -> c -> c -> null

2：遍历一遍，每到一个复制的节点，更新random pointer。

3：遍历一遍，恢复原链表，并把复制节点加入新链表。
a -> b -> c -> null
dummy -> a -> b -> c -> null

4：返回新链表。
a -> b -> c -> null


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 {
    /**
     * @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) {
        // write your code here
        
        RandomListNode iter;
        RandomListNode next;
        iter = head;
        
        while (iter != null) {
            next = iter.next;
            RandomListNode copy = new RandomListNode(iter.label);
            iter.next = copy;
            copy.next = next;
            iter = next;
        }
        
        iter = head;
        while (iter != null) {
            if (iter.random != null) {
                iter.next.random = iter.random.next;
            }
            iter = iter.next.next;
        }
        
        RandomListNode dummy = new RandomListNode(0);
        iter = head;
        RandomListNode copyIter;
        RandomListNode copy;
        copyIter = dummy;
        while (iter != null) {
            next = iter.next.next;
            
            copy = iter.next;
            copyIter.next = copy;
            copyIter = copy;
            
            iter = next;
        }
        
        return dummy.next;
    }
}