c++ 103ms solution without hash table


  • 1
    X
    class Solution {
    public:
        /**
         * @param head: The head of linked list with a random pointer.
         * @return: A new head of a deep copy of the list.
         */
        RandomListNode *copyRandomList(RandomListNode *head) {
            RandomListNode *p = head;
            while (p) {
                RandomListNode *q = new RandomListNode(p->label);
                q->next = p->next;
                p->next = q;
                p = q->next;
            }
            p = head;
            while (p) {
                if (p->random)
                    p->next->random = p->random->next;
                p = p->next->next;
            }
            RandomListNode *ret = new RandomListNode(0), *tail = ret;
            while (head) {
                tail->next = head->next;
                tail = tail->next;
                head->next = head->next->next;
                head = head->next;
            }
            return ret->next;
        }
    };
    

Log in to reply
 

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