题解 | #复杂链表的复制#

# -*- 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。

注意：

1. 第二步只有在第一步的基础上才能执行。
2. 第二步需要从复制后的链表的头依次对比label是否相等。