题解 | #复杂链表的复制#
复杂链表的复制
https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba
# -*- 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 is None: return pHead p = pHead p3 = p2 = RandomListNode(p.label) p = p.next while p is not None: p2.next = RandomListNode(p.label) p = p.next p2 = p2.next if p is None: p2.next = None p4 = p2 = p3 p = pHead while p is not None: r = p.random if r is not None: while p2 is not None and p2.label != r.label: p2 = p2.next if p2 is not None and p2.label == r.label: p3.random = p2 p3 = p3.next p2 = p4 p = p.next return p4
第一步复制链表的next。
第二步复制链表的random。
注意:
- 第二步只有在第一步的基础上才能执行。
- 第二步需要从复制后的链表的头依次对比label是否相等。