如何每日一练剑指offer中实现复杂链表的深复制？

本文共计978个文字，预计阅读时间需要4分钟。

描述：输入一个复杂链表（每个节点包含节点值，以及两个指针，一个指向下一个节点，另一个指向随机节点），请对这个链表进行深度拷贝，并返回拷贝后的链表的头结点。

输入：pythonclass Node: def __init__(self, val=0, next=None, random=None): self.val=val self.next=next self.random=random

构建链表def create_linked_list(nodes): dummy=Node() current=dummy for node in nodes: current.next=Node(node['val']) current.next.random=nodes[node['random']] current=current.next return dummy.next

深度拷贝链表def deep_copy_linked_list(head): if not head: return None

# 创建拷贝节点 dummy=Node() current=dummy original, copy=head, dummy

# 遍历原链表，建立节点关系 while original: copy.next=Node(original.val) copy.random=original.random if original.random else None original=original.next copy=copy.next

# 恢复原链表 original=head copy=dummy.next while original: copy.next.random=copy.next.random.next if original.random else None original=original.next copy=copy.next

return dummy.next

输入：python链表节点数据nodes=[ {'val': 1, 'random': 3}, {'val': 2, 'random': 1}, {'val': 3, 'random': 2}, {'val': 4, 'random': 4}, {'val': 5, 'random': 0}]

创建链表head=create_linked_list(nodes)

深度拷贝链表copy_head=deep_copy_linked_list(head)

描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。

示例:

输入:{1,2,3,4,5,3,5,#,2,#}

输出:{1,2,3,4,5,3,5,#,2,#}

解析:我们将链表分为两段，前半部分{1,2,3,4,5}为ListNode，后半部分{3,5,#,2,#}是随机指针域表示。

以上示例前半部分可以表示链表为的ListNode:1->2->3->4->5

后半部分，3，5，#，2，#分别的表示为

1的位置指向3，2的位置指向5，3的位置指向null，4的位置指向2，5的位置指向null

如下图:

示例

输入：

{1,2,3,4,5,3,5,#,2,#}

返回值：

{1,2,3,4,5,3,5,#,2,#}

思路：

正常链表的复制，从头到尾遍历链表，对于每个节点创建新的节点，赋值，并将其连接好就可以了。这道题的不同之处在于我们还要将随机指针连接好，我们创建节点的时候，有可能这个节点创建了，但是它的随机指针指向的节点没有创建，因此创建的时候只能连接指向后面的指针，无法连接随机指针。

等链表连接好了，再连接随机指针的话，我们又难以找到这个指针指向的位置，因为链表不支持随机访问。但是吧，我们待拷贝的链表可以通过随机指针访问节点，那么我们不如将拷贝后的每个节点插入到原始链表相应节点之后，这样连接random指针的时候，原始链表random指针后一个元素就是原始链表要找的随机节点，而该节点后一个就是它拷贝出来的新节点，这不就可以连上了嘛。