作业

• 有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。

请用代码（或伪代码）描述算法，并给出时间复杂度。

!

• 请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图。

作业完成

作业1

设计

时间复杂度

O(n) + O(m) = O(n)

注：n、m都是常量， 所以复杂度不表示为O(n+m) 直接表示成O(n)即可

类图

代码实现

定义链表

type LinkTable struct {
	sync.Mutex
	name string
	FirstNode *LinkNode
	LastNode  *LinkNode
	Count     int
}
func (link *LinkTable) String() string {
	iterator:= link.GetIterator()
	str := ""
	for iterator.HasNext() {
		if str == "" {
			str += "link "
			if link.name != "" {
				str += link.name
			}
			str += ": "
		}else {
			str += " -> "
		}
		str += iterator.Next()
	}
	return str
}
func NewLinkTable(str string) LinkTable {
	return LinkTable{name: str}
}
func (link *LinkTable) Add(str string) {
	link.Lock()
	defer link.Unlock()
	node := NewLinkNode(str)
	if link.LastNode != nil {
		link.LastNode.next = &node
	}
	link.LastNode = &node
	if link.FirstNode == nil {
		link.FirstNode = &node
	}
	link.Count = link.Count +1
}
func (link *LinkTable) GetIterator() LinkIterator {
	return NewLinkIterator(link)
}
type LinkNode struct {
	value string
	next *LinkNode
}
func NewLinkNode(value string) LinkNode {
	return LinkNode{value: value}
}
type LinkIterator struct {
	current LinkNode
	link    LinkTable
}
func NewLinkIterator(link *LinkTable) LinkIterator {
	return LinkIterator{link: *link}
}
func (iterator *LinkIterator) Next() string {
	if iterator.current == (LinkNode{}) {
		iterator.current = *(iterator.link.FirstNode)
		if iterator.current != (LinkNode{}) {
			return iterator.current.value
		}
	}
	value := (*iterator.current.next).value
	iterator.current = *iterator.current.next
	return value
}
func (iterator *LinkIterator) HasNext() bool {
	if iterator.current != (LinkNode{}) {
		return iterator.current.next != nil
	}else {
		return iterator.link.FirstNode != nil
	}
}
func (iterator *LinkIterator) CurrentItem() string {
	return iterator.current.value
}

作业代码

func TestWeek8Job(t *testing.T) {
	tableA := week8.NewLinkTable("A")
	tableA.Add("a")
	tableA.Add("b")
	tableA.Add("x")
	tableA.Add("y")
	tableA.Add("z")
	println(tableA.String())
	tableB := week8.NewLinkTable("B")
	tableB.Add("d")
	tableB.Add("e")
	tableB.Add("f")
	tableB.Add("x")
	tableB.Add("y")
	tableB.Add("z")
	println(tableB.String())
	m := make(map[string]string, tableA.Count)
	iteratorA := tableA.GetIterator()
	//O(n)
	for iteratorA.HasNext() {
		item := iteratorA.Next()
		m[item] = item
	}
	var target string
	iteratorB := tableB.GetIterator()
	//O(m)
	for iteratorB.HasNext() {
		item := iteratorB.Next()
		if m[item] != ""  {
			target = item
			break
		}
	}
	if target == "" {
		println("链表A与链表B无合并")
	}else {
		println("链表A与链表B从元素[",target,"]开始合并")
	}
}

运行结果

=== RUN   TestWeek8Job
link A: a -> b -> x -> y -> z
link B: d -> e -> f -> x -> y -> z
链表A与链表B从元素[ x ]开始合并
--- PASS: TestWeek8Job (0.00s)

作业2