Leetcode 138

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */

class Solution {
public:

    RandomListNode *copyRandomList(RandomListNode *head) {
       //insert nodes
        if(!head) return head;
        RandomListNode * cur = head;
        while(cur){
            RandomListNode * curClone = new RandomListNode(cur->label);
            curClone -> next = cur->next;
            cur->next=curClone;
            cur = curClone->next;
        }
        // copy random pointer
        cur = head;
        while(cur){
            if (cur->random) {
                cur->next->random = cur->random->next;
            }
            cur = cur->next->next;
        }
         //decouple two links
        cur=head;
        RandomListNode * ret=head->next;
        while(cur){
            RandomListNode * tmp = cur->next;
            cur->next=tmp->next;
            if(tmp->next){
            tmp->next=tmp->next->next;
            }
            cur=cur->next;
        }
        return ret;
    }
};

  1. 插入拷贝节点

  2. 复制random指针

  3. 分解至两个独立列表

results matching ""

    No results matching ""