Very clear java answer O(N) runtime and O(1) extra space


  • 0
    C
    1. Make each node copy after each node: A -> B -> C becomes A -> A -> B -> B -> C -> C
    2. Connect random pointers: current.next.random = current.random.next
    3. Pull apart intertwined list: current.next = current.next.next
    public class Solution {
        public RandomListNode copyRandomList(RandomListNode head) {
            if (head == null) return null;
            
            RandomListNode current = head;
            while (current != null) {
                RandomListNode copy = new RandomListNode(current.label);
                
                copy.next = current.next;
                current.next = copy;
                
                current = current.next.next;
            }
            
            current = head;
            while (current != null) {
                if (current.random == null) {
                    current.next.random = null;
                } else {
                    current.next.random = current.random.next;
                }
                current = current.next.next;
            }
            
            RandomListNode original = head;
            RandomListNode answer = head.next;
            RandomListNode currentOriginal = head;
            RandomListNode currentAnswer = head.next;
            while (currentOriginal != null && currentAnswer != null) {
                if (currentOriginal.next == null) break;
            
                currentOriginal.next = currentOriginal.next.next;
                currentOriginal = currentOriginal.next;
                
                if (currentAnswer.next == null) break;
                
                currentAnswer.next = currentAnswer.next.next;
                currentAnswer = currentAnswer.next;
            }
            
            return answer;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.