[leetcode题解]138.Copy List with Random Pointer(linked-list)

leetcode,138.copy list with random pointer.
正常的单链表中只有一个next的指针指向下一个元素的地址,本题给定一个链表,这个链表比较特殊,不仅有指向下一个元素的next指针,还有一个指向链表中随机元素的一个random指针(random pointer)。

题目要求对该链表进行拷贝,在新的拷贝中,元素的链接关系不变,注意这里的拷贝要求的是深拷贝。

由于random指针可能指向链表中的任意元素,包括NULL,所以可以建立一个指针映射。

解题步骤:

1.先考虑正常的链表,建一个新的单链表,拷贝next的整个结构,同时建立原链表节点到新链表节点的映射。
2.在链表中根据原链表以及节点映射关系,建立random随机指针。

c++代码如下:

class Solution {
//author: 凌风技术站-iaccepted
public:
    RandomListNode *copyRandomList(RandomListNode *head) 
    {
        RandomListNode *pre = new RandomListNode(-1);
        RandomListNode *tail = pre;
        map<RandomListNode *, RandomListNode *> mp;
        mp[NULL] = NULL;
        
        RandomListNode *p = head;
        while(p != NULL)
        {
            RandomListNode *node = new RandomListNode(p->label);
            mp[p] = node;
            tail->next = node;
            p = p->next;
            tail = tail->next;
        }
        
        p = head;
        tail = pre->next;
        while(p != NULL)
        {
            tail->random = mp[p->random];
            p = p->next;
            tail = tail->next;
        }
        return pre->next;
    }
};

python代码如下:

import collections


class Solution(object):

    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        :author: 凌风技术站-iaccepted
        """
        pre = RandomListNode(-1)
        tail = pre
        d = collections.defaultdict(lambda: None)

        p = head
        while p != None:
            node = RandomListNode(p.label)
            d[p] = node
            tail.next = node
            tail = tail.next
            p = p.next

        tail = pre.next
        p = head
        while p != None:
            tail.random = d[p.random]
            p = p.next
            tail = tail.next

        return pre.next

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]138.Copy List with Random Pointer(linked-list)

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/72.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注