My C++ solution (115ms, O(n) time, O(1) space)


  • 3
    D

    The algorithm needs to scan the list three time, one to copy nodes, one to copy random fields, and the last to reconnect the original list and the new list. The basic idea is to interleave the original list and the new list to facilitate the random field copy. "Interleave" means "old_node1->new_node1->old_node2->new_node_2->..."

    class Solution {
    public:
    RandomListNode *copyRandomList(RandomListNode *head) {
    RandomListNode *p1, *p2, *temp, *newHead;

            if(!head)
            {
                return NULL;
            }
            else
            {
                // generate a new list and interleave it with the original list
                p1 = head;
                while(p1)
                {
                    p2 = new RandomListNode(p1->label);
                    temp = p1->next;
                    p1->next = p2;
                    p2->next = temp;
                    p1 = temp;
                }
                
                // copy the random fields of the new list
                p1 = head;
                while(p1)
                {
                    p2 = p1->random;
                    if(p2)
                    {
                        p1->next->random = p2->next;
                    }
                    p1 = p1->next->next;
                }
                
                // separate the original and new lists
                p1 =head;
                p2 = newHead = head->next;
                while(p2->next)
                {
                    p1->next = p2->next;
                    p1= p1->next;
                    p2->next = p1->next;
                    p2 = p2->next;
                }
                p1->next = NULL;
                return newHead;
            }
        }
    };

  • 0
    M
    This post is deleted!

  • 0
    I

    I don't know why this solution cost O(1) space.
    Won't the newnode cost O(n) space?


  • 0
    I

    I think it means O(1) EXTRA space to copy random pointers.


Log in to reply
 

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