复杂链表的复制
复杂链表的复制
http://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba
按顺序分两次复制,使用map存储clone的映射关系
- 第一次,从头节点clone到尾节点,不复制random,并将原链表的地址与clone的新地址使用map映射
tmp:=make(map[*RandomListNode]*RandomListNode) root := &RandomListNode{} h2 := root h1 := head for h1 != nil{ h2.Next = &RandomListNode{h1.Label,nil,nil} tmp[h1] = h2.Next h2 = h2.Next h1 = h1.Next }
- 第二次,从头节点clone到尾节点,复制random,从映射表中获取对应的clone地址,并赋值
h2 = root.Next for head != nil{ if head.Random != nil{ h2.Random = tmp[head.Random] // fmt.Println(tmp[head.Random].Label) } h2 = h2.Next head = head.Next }