本文共 1296 字，大约阅读时间需要 4 分钟。

实现一个函数，完成复杂链表的复制功能；在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

题解分析

普通链表复制非常简单，只需遍历一遍，复制创建每个节点即可。但因此复杂链表中有一个next指针，指向不确定的节点，所以普通方式修改复制next指针时，需要在复制每个指针时遍历一遍链表；无法在O(N)时间内完成。

因链表是可以随意拼接、断开的；因此可以先把新创建的节点连接在源节点后面，在全部完成（包括设定next指针）后，再拆分为两个链表：原链表与新链表：

• 复制每一个节点，并拼接在原链表中；
• 设定新节点的random指针：指向原节点random指针指向节点的下一个节点即可；
• 拆分链表为原链表与新链表

复杂度分析：

• 时间：只需遍历三遍链表即可，所以为O(N)；
• 空间：只需常数大小的额外空间，所以为O(1)；

代码实现

节点定义：

type Node struct {
       Val    int    Next   *Node    Random *Node}

复制链表：

func copyRandomList(head *Node) *Node {
       if head == nil {
           return nil    }    // copy each node    for ori := head; ori != nil; {
           cp := &Node{
               Val:    ori.Val,            Next:   ori.Next,            Random: nil,        }        ori.Next = cp        ori = cp.Next    }    // set the random-pointer    for ori := head; ori != nil; {
           if ori.Random != nil {
               ori.Next.Random = ori.Random.Next        }        ori = ori.Next.Next    }    // construct the copy-list    pre := head.Next    result := pre    head.Next = pre.Next    for ori := pre.Next; ori != nil; {
           pre.Next = ori.Next        pre = pre.Next        ori.Next = pre.Next        ori = ori.Next    }    pre.Next = nil    return result}

转载地址：http://wzilf.baihongyu.com/