如何检测两个单链表(无环)是否交叉？

题目

单链表相交，是指两个单链表存在完全重合的部分。对于两个单链表（无环），如何检测是否交叉？

解法

用 set/map 存储并检测

和上篇文章的常规思路相似，如果交叉，则存在相同的节点。

func checkCross(head1 *LNode, head2 *LNode) bool {
	if head1 == nil || head2 == nil {
		return false
	}

	tmp := make(map[*LNode]interface{})

	// 将单链表1中的节点全部存起来
	cur1 := head1.Next
	for cur1 != nil {
		tmp[cur1] = nil
		cur1 = cur1.Next
	}
	// 遍历单链表2
	cur2 := head2.Next
	for cur2 != nil {
		if _, ok := tmp[cur2]; ok {
			// 找到相同节点
			return true
		}
		cur2 = cur2.Next
	}
	return false
}

func main() {
	node1 := &LNode{Data: 1}
	node2 := &LNode{Data: 2}
	node3 := &LNode{Data: 3}
	node4 := &LNode{Data: 4}
	node5 := &LNode{Data: 5}

	// l1: 1->2->3->4->5
	l1 := NewLList()
	l1.Next = node1
	node1.Next = node2
	node2.Next = node3
	node3.Next = node4
	node4.Next = node5

	// l2: 6->7->4->5
	l2 := NewLList()
	node6 := &LNode{Data: 6}
	node7 := &LNode{Data: 7}
	l2.Next = node6
	node6.Next = node7
	node7.Next = node4

	// l3: 8->9->10->11
	l3 := NewLList()
	node8 := &LNode{Data: 8}
	node9 := &LNode{Data: 9}
	node10 := &LNode{Data: 10}
	node11 := &LNode{Data: 11}
	l3.Next = node8
	node8.Next = node9
	node9.Next = node10
	node10.Next = node11

	isCross := checkCross(l1, l2)
    // l1与l2相交？ true
	fmt.Println("l1与l2相交？", isCross)

	isCross = checkCross(l1, l3)
    // l1与l2相交？ false
	fmt.Println("l1与l3相交？", isCross)
}

构成带环单链表

受上篇文章的启发，如果两个单链表交叉，则如果把单链表1的尾部链接到单链表2的头部，则可以构成一个带环的单链表，这时再检测是否带环就可以了。

func checkRing(head *LNode) bool {
	if head == nil || head.Next == nil {
		return false
	}

	slow := head.Next
	fast := head.Next

	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			return true
		}
	}
	return false
}

func checkCross(head1, head2 *LNode) bool {
	if head1 == nil || head2 == nil {
		return false
	}

	cur := head1.Next
	for cur.Next != nil {
		cur = cur.Next
	}
	// cur 此时是 head1的尾部，将其链接到 head2 上
	cur.Next = head2.Next

	return checkRing(head1)
}

func main() {
	node1 := &LNode{Data: 1}
	node2 := &LNode{Data: 2}
	node3 := &LNode{Data: 3}
	node4 := &LNode{Data: 4}
	node5 := &LNode{Data: 5}

	// l1: 1->2->3->4->5
	l1 := NewLList()
	l1.Next = node1
	node1.Next = node2
	node2.Next = node3
	node3.Next = node4
	node4.Next = node5

	// l2: 6->7->4->5
	l2 := NewLList()
	node6 := &LNode{Data: 6}
	node7 := &LNode{Data: 7}
	l2.Next = node6
	node6.Next = node7
	node7.Next = node4

	// l3: 8->9->10->11
	l3 := NewLList()
	node8 := &LNode{Data: 8}
	node9 := &LNode{Data: 9}
	node10 := &LNode{Data: 10}
	node11 := &LNode{Data: 11}
	l3.Next = node8
	node8.Next = node9
	node9.Next = node10
	node10.Next = node11

	// l4: 12->13->14
	l4 := NewLList()
	node12 := &LNode{Data: 12}
	node13 := &LNode{Data: 13}
	node14 := &LNode{Data: 14}

	l4.Next = node12
	node12.Next = node13
	node13.Next = node14

	isCross := checkCross(l1, l2)
	// l1与l2相交？ true
	fmt.Println("l1与l2相交？", isCross)

	isCross = checkCross(l3, l4)
	// l3与l4相交？ false
	fmt.Println("l3与l4相交？", isCross)
}