输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针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
- 难点在于如何拷贝那个随机指针
hash
- 先忽略随机指针,搞出来一个单链表副本
- 把两个新旧链表对应位置的元素做一个映射备用
- 遍历映射,如果某个新节点对应的旧节点有随机指针
- 那么先找到旧节点随机指针指向的旧节点
- 再通过映射找到这个旧节点对应的新节点
- 替黄老爷接上这条腿!
func Clone(head *RandomListNode) *RandomListNode {
if head == nil {
return nil
}
releationship := make(map[*RandomListNode]*RandomListNode)
sentry := &RandomListNode{}
pre := sentry
cur := head
for cur != nil {
newOne := &RandomListNode{
Label: cur.Label,
}
releationship[cur] = newOne
pre.Next = newOne
pre = pre.Next
cur = cur.Next
}
for origin, newOne := range releationship {
if origin.Random == nil {
newOne.Random = nil
} else {
newOne.Random = releationship[origin.Random]
}
}
return sentry.Next
}