[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 = None

class Solution:
    # @param head, a RandomListNode
    # @return a RandomListNode
    def copyRandomList(self, head):
        if head == None: return None
        tmp = head
        while tmp:
            newNode = RandomListNode(tmp.label)
            newNode.next = tmp.next
            tmp.next = newNode
            tmp = tmp.next.next
        tmp = head
        while tmp:
            if tmp.random:
                tmp.next.random = tmp.random.next
            tmp = tmp.next.next
        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

 

[leetcode]Copy List with Random Pointer @ Python,古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。