剑指offer-复杂链表的复制

一、题意

题目描述

请实现函数ComplexListNode Clone(ComplexListNode head)，复制一个复杂链表。在复杂链表中，每个结点除了有一个Next指针指向下一个结点外，还有一个Sibling指向链表中的任意结点或者NULL。

二、题解

借助辅助空间的O(n)解法

• 第一步复制原始链表上的每个结点N创建N’，然后把这些创建出来的结点用Next链接起来。同时把(N，N’)配对信息放到一个哈希表中，节点数量不多的话，用普通map也可以。

• 第二步设置复制链表上每个结点的sibling兄弟节点。由于有了哈希表，可以用O(1)的时间根据sibling找到sibling’。

三、代码实现

>folded main.go

package main

import (
	"fmt"
)

type ComplexListNode struct {
	Val  	int                 // 值
	Next 	*ComplexListNode    // 下一个节点
	Sibling *ComplexListNode    // 随机的兄弟节点
}

func CloneComplexList(head *ComplexListNode) *ComplexListNode {
	if head == nil {
		return nil
	}
	m := make(map[*ComplexListNode]*ComplexListNode)
	cur := head
	for cur != nil {
		if _, ok := m[cur]; !ok {
			m[cur] = &ComplexListNode{cur.Val, nil, nil}
		}
		if cur.Next != nil {
			if _, ok := m[cur.Next]; !ok {
				m[cur.Next] = &ComplexListNode{cur.Next.Val, nil, nil}
			}
			m[cur].Next = m[cur.Next]
		}
		if cur.Sibling != nil {
			if _, ok := m[cur.Sibling]; !ok {
				m[cur.Sibling] = &ComplexListNode{cur.Sibling.Val, nil, nil}
			}
			m[cur].Sibling = m[cur.Sibling]
		}
		cur = cur.Next
	}
	return m[head]
}

func printList(head *ComplexListNode){
	for head != nil{
		fmt.Printf("当前节点: %d 兄弟节点: %d \t", head.Val, head.Sibling.Val)
		head = head.Next
	}
}

func main() {
	// 构造链表
	l3 := &ComplexListNode{3, nil, nil}
	l2 := &ComplexListNode{2, l3, nil}
	l1 := &ComplexListNode{1, l2, nil}
	l1.Sibling = l3
	l2.Sibling = l2
	l3.Sibling = l1
	fmt.Println("复制前 --------- ")
	printList(l1)
	fmt.Println()
	fmt.Println("复制后 --------- ")
	printList(CloneComplexList(l1))
}

// 测试输出如下：
复制前 --------- 
当前节点: 1 兄弟节点: 3 	当前节点: 2 兄弟节点: 2 	当前节点: 3 兄弟节点: 1 	
复制后 --------- 
当前节点: 1 兄弟节点: 3 	当前节点: 2 兄弟节点: 2 	当前节点: 3 兄弟节点: 1 	

Process finished with exit code 0