Sweep the whole list three times. (252ms)


  • 1
    L

    Algo: Sweep the list three times.

    1. create a new copy and insert it behind the old node.

    2. update random pointer

    3. split the list into two. One is the orignial list, and the other is the answer.


    class Solution {
    public:
        RandomListNode *copyRandomList(RandomListNode *head) {
            if (head == nullptr)
    			return head;
    
    		RandomListNode * p = head;
    		while (p != nullptr) {
    			RandomListNode * copy = new RandomListNode(p->label);
    			copy->next = p->next;
    			p->next = copy;
    			p = copy->next;
    		}
    		p = head;
    		RandomListNode * q = p->next;
    		while (p != nullptr) {
    			if (p->random != nullptr) {
    				q->random = p->random->next;
    			}
    			p = q->next;
    			if (p != nullptr)
    				q = p->next;
    		}
    		RandomListNode * ans = head->next;
    		p = head;
    		q = p->next;
    		while (p != nullptr) {
    			p->next = q->next;
    			if (q->next != nullptr)
    				q->next = q->next->next;
    			p = p->next;
    			q = q->next;
    		}
    		return ans;
        }
    };

Log in to reply
 

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