Detailed explanation of Golang's method of determining whether two linked lists intersect

Algorithm Question: Determine the intersection of two linked lists

I'll summarize the algorithm questions you may ask during the interview today

Method 1: map

step:

1. Iterate over list1 and put the node as key into the map
2. traversal list2 to determine whether each node is in the map. If it is, it intersects, and the top node is the intersection point

// Define the linked list nodetype Node struct {
	val  int
	next *Node
}

// Determine whether two linked lists intersectfunc IsIntersect(list1, list2 *Node) bool {
	if list1 == nil || list2 == nil {
		return false
	}

	m := make(map[*Node]struct{})
	p := list1
	for p != nil {
		m[p] = struct{}{}
		p = 
	}

	p = list2
	for p != nil {
		if _, ok := m[p]; ok {
			return true
		}
		p = 
	}

	return false
}

// Generate a linked table based on the arrayfunc New(data []int) *Node {
	nodes := make([]*Node, len(data))
	for i := 0; i &lt; len(data); i++ {
		nodes[i] = &amp;Node{
			val: data[i],
		}
		if i &gt; 0 {
			nodes[i].next = nodes[i-1]
		}
	}

	return nodes[len(data)-1]
}

// Merge two linked listsfunc Connect(node1, node2 *Node) *Node {
	if node1 == nil {
		return node2
	}

	if node2 == nil {
		return node1
	}

	p := node1
	for  != nil {
		p = 
	}

	 = node2
	return node1
}

test

func main() {
	data1 := []int{1, 2, 3, 4, 5}
	data2 := []int{6, 7, 8, 9, 10}
	data3 := []int{11, 12, 13, 14, 15}

	node1 := New(data1)
	node2 := New(data2)
	node3 := New(data3)

	node2 = Connect(node2, node1)  // 10,9,8,7,6,5,4,3,2,1
	node3 = Connect(node3, node1)  // 15,14,13,12,11,5,4,3,2,1

	result := (node2, node3)
	(result) // true
}

Method 2: Head-to-tail connection method

Point the tail of linked list 1 to the header, then traverse linked list 2 to see if it can reach the header of linked list 1. If so, it means intersecting.

func IsIntersect(list1, list2 *Node) bool {
	if list1 == nil || list2 == nil {
		return false
	}

	// Point the tail of linked list 1 to the head	p := list1
	for  != nil {
		p = 
	}
	 = list1

	// traverse linked list 2. If the header of linked list 1 can be reached, it means that it will intersect.	p = list2
	for p != nil {
		if p == list1 {
			return true
		}

		p = 
	}

	return false
}

This is the article about this detailed explanation of the method of Golang to determine whether two linked lists intersect. For more relevant content on Golang to determine whether linked lists intersect, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!