首页 > 代码库 > [leetcode]Copy List with Random Pointer @ Python
[leetcode]Copy List with Random Pointer @ Python
原题地址：https://oj.leetcode.com/problems/copy-list-with-random-pointer/
题意：
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.
解题思路：这题主要是需要深拷贝。看图就明白怎么写程序了。
第一步，在原链表的每个节点后面都插入一个新节点，新节点的内容和前面的节点一样。比如上图，1后面插入1，2后面插入2，依次类推。
第二步，原链表中的random指针如何映射呢？比如上图中，1节点的random指针指向3，4节点的random指针指向2。如果有一个tmp指针指向1（蓝色），则一条语句：tmp.next.random = tmp.random.next；就可以解决这个问题。
第三步，将新的链表从上图这样的链表中拆分出来。
代码：
# Definition for singly-linked list with a random pointer.# class RandomListNode:# def __init__(self, x):# self.label = x# self.next = None# self.random = Noneclass Solution: # @param head, a RandomListNode # @return a RandomListNode def copyRandomList(self, head): #http://www.cnblogs.com/zuoyuan/p/3745126.html if head == None: return None # Step 1: duplicate nodes in order tmp = head while tmp: newNode = RandomListNode(tmp.label) newNode.next = tmp.next tmp.next = newNode tmp = tmp.next.next # Step 2: preseve random pointer tmp = head while tmp: if tmp.random: tmp.next.random = tmp.random.next # assign the old node‘s random pointer to new duplicated node‘s random filed tmp = tmp.next.next # Step 3: extract new list and return newhead = head.next pold = head pnew = newhead while pnew.next: pold.next = pnew.next pold = pold.next pnew.next = pold.next pnew = pnew.next pold.next = None pnew.next = None return newhead
参考：
http://www.cnblogs.com/zuoyuan/p/3745126.html
[leetcode]Copy List with Random Pointer @ Python
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。