[算法]剑指offer p26复杂链表的复制 golang

题目

题目：请实现函数Clone，复制一个复杂链表。在复杂链表中，每个结点除了有一个next指针指向下一个结点外，还有一个sub指向链表中的任意结点或者NULL。结点的 golang 定义如下：

type ComplexLinkNode struct {
	Value int
	Next  *ComplexLinkNode
	Sub   *ComplexLinkNode
}

//复杂链表的复制
func (h *ComplexLinkNode) Clone() (newHead *ComplexLinkNode) {
	//todo
	return
}

如上图所示, 黑色箭头是 next 指针, 绿色箭头是 sub 指针

例如节点1的 next 指向节点2, 节点4 的 next 指向自身

解法1

思路:

先使用 next ,复制一条新链表, 使用 map 构建旧链表到新链表的映射, 再连接 sub 的节点

时间复杂度是 O(n)

如果第一次复制 next 节点, 新的链表的 sub 指针还是指向的旧链表, 所以是不行的, 第二次复制 sub 节点就需要通过 value 遍历新链表(时间复杂度是 O(n2)), 而且 value 重复还会导致复制错误.

代码

// 记录当前路径总和
type ComplexLinkNode struct {
	Value int
	Next  *ComplexLinkNode
	Sub   *ComplexLinkNode
}

//复杂链表的复制
//复杂链表不得是环形链表,将会死循环 todo: 死循环处理
func (h *ComplexLinkNode) Clone() (newHead *ComplexLinkNode) {
	//参数处理
	if h == nil {
		fmt.Printf("%s\n", "err: h==nil")
		return nil
	}
	//复制 next 指针,并使用 hashmap 映射
	hashMap := make(map[*ComplexLinkNode]*ComplexLinkNode)
	newHead = &ComplexLinkNode{Value: h.Value, Next: h.Next, Sub: h.Sub}
	hashMap[h] = newHead
	tempNode := newHead
	for {
		//退出条件
		if tempNode.Next == nil {
			break
		}
		//复制链表
		oldNode := tempNode.Next
		tempNode.Next = &ComplexLinkNode{Value: tempNode.Next.Value, Next: tempNode.Next.Next, Sub: tempNode.Next.Sub}
		//hash 映射
		hashMap[oldNode] = tempNode.Next
		//下一个节点
		tempNode = tempNode.Next
	}
	//2. 使用 hashmap 复制 sub 指针
	tempNode = newHead
	tempNode.Sub = hashMap[tempNode.Sub]
	for {
		//退出条件
		if tempNode.Next == nil {
			break
		}
		//sub 指针
		tempNode.Next.Sub = hashMap[tempNode.Next.Sub]
		//下一个节点
		tempNode = tempNode.Next
	}
	return 
}

测试

package main

import (
	"fmt"
	"testing"

	"github.com/stretchr/testify/assert"
)

func TestP26(t *testing.T) {
	n1 := &ComplexLinkNode{Value: 1, Next: nil, Sub: nil}
	n2 := &ComplexLinkNode{Value: 1, Next: nil, Sub: nil}
	n3 := &ComplexLinkNode{Value: 1, Next: nil, Sub: nil}
	n4 := &ComplexLinkNode{Value: 1, Next: nil, Sub: nil}
	n1.Next = n2
	n2.Next = n3
	n3.Next = n4
	n1.Sub = n3
	n2.Sub = n4
	n3.Sub = n1
	n4.Sub = n1
	cln := n1.Clone()
	assert.Equal(t, n1, cln)
}