-
Notifications
You must be signed in to change notification settings - Fork 558
/
复杂链表的复制.py
63 lines (55 loc) · 2.2 KB
/
复杂链表的复制.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
'''
题目:输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),
返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
'''
'''
思路:1. 根据旧链表创建新链表,不去管随机的那个指针
2. 根据旧链表中的随机指针,创建新链表中的随机指针
3. 从旧链表中拆分得到新链表
32ms
5632k
'''
# -*- coding:utf-8 -*-
class RandomListNode:
def __init__(self, x):
self.label = x
self.next = None
self.random = None
class Solution:
# 返回 RandomListNode
def Clone(self, pHead):
if pHead == None:
return None
self.CloneNodes(pHead)
self.ConnectRandomNodes(pHead)
return self.ReconnectNodes(pHead)
# 复制原始链表的每个结点, 将复制的结点链接在其原始结点的后面
def CloneNodes(self, pHead):
pNode = pHead
while pNode:
pCloned = RandomListNode(0)
pCloned.label = pNode.label
pCloned.next = pNode.next
# pCloned.random = None #不需要写这句话, 因为创建新的结点的时候,random自动指向None
pNode.next = pCloned
pNode = pCloned.next
# 将复制后的链表中的复制结点的random指针链接到被复制结点random指针的后一个结点
def ConnectRandomNodes(self, pHead):
pNode = pHead
while pNode:
pCloned = pNode.next
if pNode.random != None:
pCloned.random = pNode.random.next
pNode = pCloned.next
# 拆分链表, 将原始链表的结点组成新的链表, 复制结点组成复制后的链表
def ReconnectNodes(self, pHead):
pNode = pHead
pClonedHead = pClonedNode = pNode.next
pNode.next = pClonedHead.next
pNode = pNode.next
while pNode:
pClonedNode.next = pNode.next
pClonedNode = pClonedNode.next
pNode.next = pClonedNode.next
pNode = pNode.next
return pClonedHead