论坛首页 编程语言技术论坛

[Leetcode] Copy List with Random Pointer

浏览 2108 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2013-10-05  

Copy List with Random Pointer

 
AC Rate: 350/1573
My Submissions

 

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

 

 

/**
 * 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) {
        if (head == NULL) return NULL;
        RandomListNode* cur = head;
        while (cur != NULL) {
            RandomListNode* x = new RandomListNode(cur->label);
            x->next = cur->next;
            cur->next = x;
            cur = x->next;
        }
        
        cur = head;
        while (cur != NULL) {
            if (cur->random != NULL) cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        RandomListNode myhead(99);
        cur = head;
        RandomListNode* newcur = &myhead;
        while (cur != NULL) {
            newcur->next = cur->next;
            newcur = newcur->next;
            cur->next = cur->next->next;
            cur = cur->next;
        }
        newcur->next = NULL;
        return myhead.next;
    }
};

 

论坛首页 编程语言技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics