【面试题26】复杂链表的复制
【题目描述】输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
【思路】
1.链表复制
2.链表兄弟节点复制
3.链表奇偶分离
文章图片
image.png 【【面试题26】复杂链表的复制】代码:
# 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 pHead
curNode = pHead
#复制链表
while curNode!=None:
newNode = RandomListNode(curNode.label)
newNode.next = curNode.next
curNode.next = newNode
curNode = newNode.next
#复制兄弟节点
curNode = pHead
while curNode!=None:
if curNode.random!=None:
curNode.next.random = curNode.random.next
curNode = curNode.next.next
#新旧链表分离,奇偶分离
head = pHead.next
cur = head
#将新旧链表分离
pCur = pHead
while(pCur != None):
pCur.next = pCur.next.next
if cur.next != None:
cur.next = cur.next.next
cur = cur.next
pCur = pCur.next
return head
推荐阅读
- 2019-04-18-|2019-04-18- 完结
- 网课成长与反思——1809王浩阳|网课成长与反思——1809王浩阳 -
- 【smart-transform】取自|【smart-transform】取自 Atom 的 babeljs/coffeescript/typescript 智能转 es5 库
- 【乐活育儿咨询】孩子的问题,源自妈妈焦虑的状态,如何破()
- 夏趣(末篇)
- 9.7责任分散
- 主持人课程第二天总结
- 一场疫情,隔离了我所有的梦想
- 【晨写04】那只路边的蚂蚁,准吓坏了
- 该有的会有的