首页 > 代码库 > 138. Copy List with Random Pointer
138. Copy List with Random Pointer
https://leetcode.com/problems/copy-list-with-random-pointer/#/description
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.
Sol 1:
# Definition for singly-linked list with a random pointer. # class RandomListNode(object): # def __init__(self, x): # self.label = x # self.next = None # self.random = None class Solution(object): def copyRandomList(self, head): """ :type head: RandomListNode :rtype: RandomListNode """ # Time O(2n) Space O(1) dic = dict() m = n = head # m is to copy label data structure, one pass. Time O(n) while m: dic[m] = RandomListNode(m.label) m = m.next # n is to copy next and random data structure. one pass. Time O(n) while n: dic[n].next = dic.get(n.next) dic[n].random = dic.get(n.random) n = n.next return dic.get(head)
Note:
1 In the initlization of a linked list,
self.label = x
"label" here mean value.... it‘s a name, does not matter
Sol 2:
# Definition for singly-linked list with a random pointer. # class RandomListNode(object): # def __init__(self, x): # self.label = x # self.next = None # self.random = None import collections class Solution(object): def copyRandomList(self, head): """ :type head: RandomListNode :rtype: RandomListNode """ # Time O(n) Space O(1) # Nice lambda initlization here. Pythonic dic = collections.defaultdict(lambda : RandomListNode(0)) dic[None] = None n = head while n: dic[n].label = n.label dic[n].next = dic[n.next] dic[n].random = dic[n.random] n = n.next return dic.get(head)
138. Copy List with Random Pointer
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。