复制复杂链表


复制复杂链表——递归与非递归

定义树的结点如下,该结点不仅有一个next指针,而且还有一个指向任意结点的指针。实现一个clone函数。该结点形成的链表形式如下图:
链表

结点

type ComListNode struct {
    value   int
    next    *ComListNode
    slibing *ComListNode
}

解题思路

在复杂链表的结点中除了next指针还有一个指向一个任意结点的指针,指向的结点有可能在该结点的前方,也有可能在该结点的后方,为了解决这个问题,我们可以将复制过程分成多个步骤,首先我们可以只复制每个结点,包含next指针,但是我们不能把该结点形成的链表单独拿出来,因为我们还要继续复制任意结点的指针,我们必须知道被复制的结点,比如上图中的A结点,复制成了一个A’,那么必须能根据A’找到A的位置,才能迅速定义到C。因此我们可以复制成结点成如下链表。
链表

所以当我们遍历到A’,A的slibing.next指针就是A’的slibing,最后我们仅仅分离出复制结点就行了。

链表

三步递归

复制结点

func CopyNode(head *ComListNode) {
    copy := new(ComListNode)
    copy.value = head.value
    copy.next = head.next
    copy.slibing = nil
    head.next = copy
    CopyNode(copy.next)
}

复制任意结点指针

func CopyComNode(head *ComListNode) {
    if head == nil {
        return
    }
    pclone := head.next
    if head.slibing != nil {
        pclone.slibing = head.slibing.next
    }
    CopyComNode(pclone.next)
}

分离出链表

// 拆分成两个链表,返回复制的链表
// 将偶数结点相连起来
func getCopy(head *ComListNode) (pcopy *ComListNode) {
    if head == nil {
        return
    }

    pcopy = head.next
    pcopy.next = getCopy(pcopy.next)
    return pcopy
}

关于非递归解法请查看github仓库


文章作者: 陌无崖
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 陌无崖 !
 上一篇
计算机操作系统——锁的进化 计算机操作系统——锁的进化
导语相信大家都知道金鱼是不知道饥饿的,如果有食物吃,金鱼就会不停的填饱肚子,哪怕被撑死。在计算机中锁的进化可以用金鱼生存的例子来引入。 金鱼生存左一和右尔共同养了一条金鱼,该金鱼每天仅仅喂食一次,如果多喂了一次,鱼会被撑死,如果没有喂金鱼,
下一篇 
顺序打印矩阵 顺序打印矩阵
顺时针打印矩阵1 2 3 45 6 7 89 10 11 1213 14 15 16 思路定义四个边界打印顺序: 1,2,3 右边界至3 4,8 12 底部边界至12 16 15 14 左边界至14 13 9 5 上边界至
  目录