{1,2,3,4,5,3,5,#,2,#}{1,2,3,4,5,3,5,#,2,#}#根据大佬思路写的python版本class Solution: def Clone(self, pHead): #用字典储存旧节点和新节点的对应关系 map = {None:None} cur = pHead while cur: map[cur] = RandomListNode(cur.label) cur = cur.next #再把新节点的next和random填上 cur = pHead while cur: map[cur].next = map[cur.next] map[cur].random = map[cur.random] cur = cur.next return map[pHead]
# 字典存储节点映射
def Clone(self, pHead):
if pHead is None:
return
np = RandomListNode(-1)
p = np
h = pHead
re = {}
while h is not None:
q = RandomListNode(h.label)
re[h] = q
p.next = q
p = p.next
h = h.next
p = np.next
h = pHead
while p is not None and h is not None:
if h.random is not None:
p.random = re[h.random]
p = p.next
h = h.next
ret = np.next
np.next = None
return ret # -*- 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): # write code here if not pHead: return None # 复制结点 pNode = pHead while pNode: pNext = pNode.next pCopy = RandomListNode(pNode.label) pNode.next = pCopy pCopy.next = pNext pNode = pNext # 定位random pNode = pHead while pNode: pRandom = pNode.random if pRandom: pNode.next.random = pRandom.next pNode = pNode.next.next # 拆分两链表 pNode = pHead pHead2 = pHead.next while pNode: pNode2 = pNode.next pNode.next = pNode2.next if pNode2.next: pNode2.next = pNode.next.next pNode = pNode.next return pHead2
import copy class Solution: # 返回 RandomListNode def Clone(self, pHead): # write code here return copy.deepcopy(pHead)
详细解释：
1.复制原节点-首先用A的值A.value创建节点A'，然后用A'→B，最后A→A'，循环复制好所有的节点
2.根据旧链表的random指向，复制新链表的random指向。A.random.next = A.next.random
3.打断链表，拆分出原链表和新的复制链表，用两个指针，一个更新总链表，一个更新复制链表，A→B，A'→B'，然后指针均往后移动一个next
# -*- 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):
# write code here
if pHead == None:
return None
# 复制node并且添加到之前链表node的后面
pTmp = pHead
while pTmp:
node = RandomListNode(pTmp.label)
node.next = pTmp.next
pTmp.next = node
pTmp = node.next
pTmp = pHead
while pTmp:
if pTmp.random:
pTmp.next.random = pTmp.random.next
pTmp = pTmp.next.next
# 断开原来的node，连接新的node
# 拆分链表，奇数上的是原列表，偶数上的是复制的新列表
pTmp = pHead
newHead = pTmp.next
pNewTmp = pTmp.next
while pTmp:
pTmp.next = pTmp.next.next
if pNewTmp.next:
pNewTmp.next = pNewTmp.next.next
pNewTmp = pNewTmp.next
pTmp = pTmp.next
return newHead递归法：
# -*- 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):
# write code here
if pHead == None:
return None
if pHead:
newHead = RandomListNode(pHead.label)
newHead.random = pHead.random
newHead.next = self.Clone(pHead.next)
return newHead
class Solution: # 返回 RandomListNode def Clone(self, pHead): # write code here if not pHead: return None new_node = RandomListNode(pHead.label) new_node.random = pHead.random new_node.next = self.Clone(pHead.next) return new_node
# -*- 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): # write code here if not pHead: return cp = RandomListNode(pHead.label) cp.random = RandomListNode(pHead.random.label) if pHead.random else None go = pHead.next ef = cp while go: ef.next = RandomListNode(go.label) ef.next.random = RandomListNode(go.random.label) if go.random else None ef = ef.next go = go.next return cp
class Solution: def Clone(self, head): cur = head # 横向复制了链表 while cur: tmp = cur.next cur.next = RandomListNode(cur.label) cur.next.next=tmp cur = tmp cur = head # 重新定向random while cur: if cur.random: cur.next.random=cur.random.next cur = cur.next.next cur = head # 拆链表 newHead = RandomListNode(0) tmp=newHead while cur: tmp.next = cur.next cur.next=cur.next.next cur=cur.next # 把原来的链表改回去，不然在牛客网的验证里会出错 tmp=tmp.next return newHead.next
用dict存储原节点和复制的节点的对应关系，那么有 A的复制的random/next = A的random/next的复制
当然，如果random指向的节点不一定在链表上，直接当有向图做就好，可以参考 马客(Mark) 的做法
# -*- coding:utf-8 -*-
class Solution:
# 返回 RandomListNode
def Clone(self, pHead):
if pHead == None:
return None
# 用dict存储原节点和复制的节点的对应关系，那么有 A的复制的random = A的random的复制
d = dict()
p = pHead
# 注意循环链表的可能
while p and p not in d:
copy_node = RandomListNode(p.label)
d[p] = copy_node
p = p.next
p = pHead
s = set()
while p and p not in s:
s.add(p)
if p.next:
d[p].next = d[p.next]
if p.random:
d[p].random = d[p.random]
p = p.next
return d[pHead]
class Solution:
# 返回 RandomListNode
def Clone(self, pHead):
# write code here
if pHead is None:
return None
clone_assis = {}
newHead = RandomListNode(pHead.label)
newHeadpointer = newHead
nexHead = pHead.next
radHead = pHead.random
clone_assis[pHead] = newHead
while nexHead is not None:
if nexHead in clone_assis:
newHeadpointer.next = clone_assis.get(nexHead)
elif nexHead is not None:
tmp = RandomListNode(nexHead.label)
clone_assis[nexHead] = tmp
newHeadpointer.next = tmp
else:
newHeadpointer.next = None
if radHead in clone_assis:
newHeadpointer.random = clone_assis.get(radHead)
#print(radHead.label)
elif radHead is not None:
tmp = RandomListNode(radHead.label)
clone_assis[radHead] = tmp
newHeadpointer.random = tmp
else:
newHeadpointer.random = None
radHead = nexHead.random
nexHead = nexHead.next
newHeadpointer = newHeadpointer.next
return newHead 
# -*- 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): # write code here if not pHead: return None # 第一步：在原链表每个节点的后面添加一个复制的节点 tmp = pHead while tmp: node = RandomListNode(tmp.label) node.next = tmp.next tmp.next = node tmp = node.next # 第二步：为每个复制的节点添加random tmp = pHead while tmp: if tmp.random: tmp.next.random = tmp.random.next tmp = tmp.next.next # 第三步：将含有复制节点的链表分割为两个链表，原始链表和新链表 tmp = pHead res = tmp.next while tmp.next: p1 = tmp.next tmp.next = p1.next tmp = p1 return res
python用字典解题
class Solution:
# 返回 RandomListNode
def Clone(self, pHead):
# write code here
if not pHead:
return
ppHead = pHead
hashtab = {None:None}
while pHead:
node = RandomListNode(pHead.label)
hashtab.update({pHead: node})
pHead = pHead.next
for k in hashtab:
if k:
hashtab[k].next = hashtab[k.next]
hashtab[k].random = hashtab[k.random]
return hashtab[ppHead] class Solution: def Clone(self, head): nodeList = [] # 存放各个节点 randomList = [] # 存放各个节点指向的random节点。没有则为None labelList = [] # 存放各个节点的值 #遍历整个链表 while head: randomList.append(head.random) nodeList.append(head) labelList.append(head.label) head = head.next # random节点的索引，如果没有则为-1，返回的是节点的random指针指向的链表的位置 #node节点对应的random节点的位置 labelIndexList = map(lambda c: nodeList.index(c) if c else -1, randomList) #此处设定的是空的头节点 dummy = RandomListNode(0) pre = dummy # 节点列表，只要把这些节点的random设置好，顺序串起来就ok了。 #很简单的一个创建新链表的过程 nodeList = map(lambda c: RandomListNode(c), labelList) # 把每个节点的random绑定好，根据对应的index来绑定 for i in range(len(nodeList)): if labelIndexList[i] != -1: nodeList[i].random = nodeList[labelIndexList[i]] for i in nodeList: pre.next = i pre = pre.next #既改变了dummy所引导的链表，但是又没有改变链表头 return dummy.next
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
