138. Copy List with Random Pointer

[3RD TRY]
Version #2 Space O(1)

99.46 %
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;
        RandomListNode curr = head;
        RandomListNode next = null;
     
        while (curr != null) {
            next = curr.next;
            curr.next = new RandomListNode(curr.label);
            curr.next.next = next;
            curr = next;
        }
        // 1 -> 1' -> null
        curr = head;
        while (curr != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next;
            }
            curr = curr.next.next;
        }
        RandomListNode result = head.next;
        curr = head;
        RandomListNode newCurr = head.next;
        RandomListNode newNext = null;
        // curr newCurr next newNext
        // c1 -> c1' -> c2 -> c2'
        while (curr != null) {
            next = curr.next.next;
            if (next != null) {
                newNext = next.next;
            } else {
                newNext = null;
            }
            curr.next = next;
            newCurr.next = newNext;
            curr = next;
            newCurr = newNext;
        }
        return result;
    }
}



Version #1 additional O(n) space complexity
/**
 * 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
        if (head == null) return head;
        //RandomListNode newHead = new RandomListNode(head.val);
        Map<RandomListNode, RandomListNode> hash = new HashMap<>();
        RandomListNode curr = head;
        while (curr != null) {
            hash.put(curr, new RandomListNode(curr.label));
            curr = curr.next;
        }
        curr = head;
        RandomListNode newCurr;
        while (curr != null) {
            newCurr = hash.get(curr);
            newCurr.next = hash.get(curr.next);
            newCurr.random = hash.get(curr.random);
            curr = curr.next;
        }
        return hash.get(head);
    }
}

二刷
41.34 %
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;
        //HashMap<key-origional node, value-new node>
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode curr = head;
        while (curr != null) {
            map.put(curr, new RandomListNode(curr.label));
            curr = curr.next;
        }
        curr = head;
        RandomListNode newNode;
        while (curr != null) {
            newNode = map.get(curr);
            newNode.next = map.get(curr.next);
            newNode.random = map.get(curr.random);
            curr = curr.next;
        }
        return map.get(head);
    }
}



Version #2 Copy the original list
Using next pointer as the hashmap
O(1) space complexity
beats 66.88%   faster than version #1
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
        if (head == null) return head;
        RandomListNode curr = head;
        RandomListNode nextNode = null;
        while (curr != null) {
            nextNode = curr.next;
            curr.next = new RandomListNode(curr.label);
            curr.next.next = nextNode;
            curr = nextNode;
        }
        curr = head;
        while (curr != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next;
            }
            curr = curr.next.next;
        }
        //split
        //   newCurr curr
        // 1    1' ->null -> 2'
        // |          |
        // ----------->
        RandomListNode newHead = head.next;
        RandomListNode newCurr = newHead;
        curr = head;
        while (curr != null) {
            curr.next = newCurr.next;
            curr = curr.next;
            if (curr != null) {
                newCurr.next = curr.next;
                newCurr = newCurr.next;
            }
        }
        return newHead;
    }
}

二刷
74.36 %
跟上面写的一样
唯一的bug还是没有考虑random可能是null的情况
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        //1.Insert copied nodes
        //2.Copy random pointers
        //3.Split lists
        // 1->1'->2->2'->3->3'->4->4'
        //curr
        //head
        //newHead
        if (head == null) return head;
        RandomListNode curr = head;
        RandomListNode temp;
        while (curr != null) {
            temp = curr.next;
            curr.next = new RandomListNode(curr.label);
            curr.next.next = temp;
            curr = temp;
        }
        curr = head;
        while (curr != null && curr.next != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next;
            }
            curr = curr.next.next;
        }
        RandomListNode newHead = head.next;
        RandomListNode newCurr = newHead;
        curr = head;
        while (curr != null && curr.next != null) {
            // 1->->2 |  ->3->3'->4->4'
            //     curr
            //    1'->2'
            curr.next = curr.next.next;
            curr = curr.next;4
            if (curr != null) {
                newCurr.next = curr.next;
                newCurr = newCurr.next;
            }
        }
        return newHead;
    }
}