A solution with constant space complexity O(1) and linear time complexity O(N)


  • 317
    L

    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.

    1. Iterate the original list and duplicate each node. The duplicate
      of each node follows its original immediately.
    2. Iterate the new list and assign the random pointer for each
      duplicated node.
    3. Restore the original list and extract the duplicated nodes.

    The algorithm is implemented as follows:

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

  • 0
    D

    Very cool solution! Many thanks!


  • 0
    W

    A smart idea.


  • 75
    C

    Great solution, but it is not O(1) space, you can argue that no extra data structure is used, but it's still O(n) space.


  • 0
    S

    Smart solution :D Thank you :)


  • 18
    Z

    You need at least O(n) space to keep the list copy, which is for the output. So IMHO, it is correct to say that the space complexity is O(1).


  • 0
    E

    you altered the structure of the given link list , although you put it back at the end I don't know if it is allowed . But it is smart though.


  • 2
    L

    Technically, it is still O(n) space complexity, and this is the min space required. But, it is truly O(1) extra space. good solution.


  • 0
    T

    essentially you ARE still using a hash table, but were reusing the "next" pointer of the original list, in a time-divided fashion


  • 14

    Very nice idea! After reading the idea, I wrote it in Python and then compared it to your code. Not surprisingly, it's very similar, but also a little different.

    def copyRandomList(self, head):
    
        # Insert each node's copy right after it, already copy .label
        node = head
        while node:
            copy = RandomListNode(node.label)
            copy.next = node.next
            node.next = copy
            node = copy.next
    
        # Set each copy's .random
        node = head
        while node:
            node.next.random = node.random and node.random.next
            node = node.next.next
    
        # Separate the copied list from the original, (re)setting every .next
        node = head
        copy = head_copy = head and head.next
        while node:
            node.next = node = copy.next
            copy.next = copy = node and node.next
    
        return head_copy
    

  • 2

    Wow, after running your solution on some examples, I could only wonder how could you come up with such a clever idea :-)

    I rewrite the code in C++ as follows.

    class Solution { 
    public:
        RandomListNode *copyRandomList(RandomListNode *head) {
            if (!head) return NULL;
            RandomListNode* run = head;
            /* Insert the copy of each node after it. */
            while (run) {
                RandomListNode* copy = new RandomListNode(run -> label);
                copy -> next = run -> next;
                run -> next = copy;
                run = run -> next -> next;
            }
            /* Set the random pointer for each copy. */
            run = head;
            while (run) {
                if (run -> random)
                    run -> next -> random = run -> random -> next;
                run = run -> next -> next;
            }
            /* Extract the copy list. */
            RandomListNode* new_head = new RandomListNode(0);
            RandomListNode* new_run;
            run = head;
            new_head -> next = head -> next;
            while (run) {
                new_run = run -> next;
                run -> next = new_run -> next;
                if (run -> next)
                    new_run -> next = new_run -> next -> next;
                run = run -> next;
            }
            return new_head -> next;
        }
    };

  • 0

    Hi, ChuntaoLu. In fact, I think you are correct. According to this link, space complexity means how much memory, in the worst case, is needed at any point in the algorithm. And this algorithm is of O(n) space in this sense. It is actually O(1) extra space but is still O(n) space. Well, it is unlucky that you got downvotes for a correct opinion...


  • -1
    This post is deleted!

  • -1
    R

    Is it possible that there is circle in the list? In that case the first round will never stop.


  • 1

    Possibly not. If it has a circle, the OJ judging will also not stop. That makes no sense and great trouble...


  • 0
    D

    Upvote. It's true that the solution by iaison is beautiful, but the space complexity is still o(N), since we create N new nodes


  • -1
    K

    Single pass solution. For every node, we check if its next and random has been copied. If not, we create the copies and store them into the map. To prevent creating duplicate copies, at the start of the while loop, we always start by checking if the cur node has already been added.

    public class Solution {
        public RandomListNode copyRandomList(RandomListNode head) {
            HashMap<RandomListNode,RandomListNode> map = new HashMap<RandomListNode,RandomListNode>();
            RandomListNode cur = head;
            while(cur != null) {
                RandomListNode newCur = null;
                if(map.containsKey(cur)) {
                    newCur = map.get(cur);
                } else {
                    newCur = new RandomListNode(cur.label);
                    map.put(cur, newCur);
                }
                
                RandomListNode newNext = null;
                if(cur.next != null) {
                    if(map.containsKey(cur.next)) {
                        newNext = map.get(cur.next);
                    } else {
                        newNext = new RandomListNode(cur.next.label);
                        map.put(cur.next, newNext);
                    }
                }
                
                RandomListNode newRand = null;
                if(cur.random != null) {
                    if(map.containsKey(cur.random)) {
                        newRand = map.get(cur.random);
                    } else {
                        newRand = new RandomListNode(cur.random.label);
                        map.put(cur.random, newRand);
                    }
                }
                
                newCur.next = newNext;
                newCur.random = newRand;
                cur = cur.next;
            }
            return map.get(head);
        }
    }

  • 1
    G

    why do we need 3 iterations ? can't we do the operations in the third step along with the 2nd step ?


  • -1
    M

    Since we are required to create a deep copy, it's impossible not to allocate memory. So it's meaningless to put a space complexity limit for this problem ( whether n or 2n is not big difference).


  • 5
    P

    Correct me if I am wrong. Originally the random variable points to the nodes of the original list. When you assign randoms for the new cloned list, it seems to me that you are referencing to the original list's nodes. Don't you need to reference to the cloned list's cloned nodes instead?


Log in to reply
 

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