牛客剑指offer第二十五题（复杂链表的复制）

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

解题思路

先将新链表的所有结点通过next指针连接起来，在连接的同时记录下每个结点的random指针，然后在将新链表各个结点的random指针连接起来。

代码实现

from collections import defaultdict
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        if pHead is None:
            return pHead
        newhead = RandomListNode(pHead.label)
        cur = pHead
        new_cur = newhead
        dic = defaultdict()
        # next指针连接新链表的所有指针，同时记录下所有结点的random指针指向的结点的结点值
        while cur.next:
            new_cur.next = RandomListNode(cur.next.label)
            new_cur = new_cur.next
            cur = cur.next
            dic[new_cur.label] = new_cur
        cur_ = pHead
        new_cur_ = newhead
        # 基于记录的random指针列表，将新链表的各个结点的random指针一一连接
        while cur_:
            if cur_.random:
                new_cur_.random = dic[cur_.random.label]
            new_cur_ = new_cur_.next
            cur_ = cur_.next
        return newhead