首页 > 其他 > 详细

Copy List with Random Pointer leetcode

时间:2016-01-15 22:41:15      阅读:227      评论:0      收藏:0      [点我收藏+]

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.

 

Subscribe to see which companies asked this question

技术分享

1、在链表中依次插入新的结点
2、构建新节点random指针:newNode->random = oldNode->random->next
3、恢复原始链表以及构建新链表:例如old->next = old->next->next,  new->next = new->next->next
 
RandomListNode *copyRandomList(RandomListNode *head) {
    if (head == nullptr)
        return nullptr;
    RandomListNode *iter = head;
    while (iter != nullptr)
    {
        RandomListNode *newNode = new RandomListNode(iter->label);
        newNode->next = iter->next;
        iter->next = newNode;
        iter = newNode->next;
    }
    iter = head;
    RandomListNode *iter1;
    while (iter != nullptr)
    {
        iter1 = iter->next;
        if(iter->random != nullptr)
            iter1->random = iter->random->next;
        iter = iter1->next;
    }
    RandomListNode *ret;
    ret = head->next;
    iter1 = ret;
    head->next = ret->next;
    iter = head->next;
    while (iter != nullptr)
    {
        iter1->next = iter->next;
        iter1 = iter1->next;
        iter->next = iter1->next;
        iter = iter->next;
    }
    return ret;
}

 

Copy List with Random Pointer leetcode

原文:http://www.cnblogs.com/sdlwlxf/p/5134463.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!