golang力扣leetcode 160.相交链表

160.相交链表

160.相交链表

题解

思路1：

1.用map存A的所有节点，赋值为true
2.遍历B的节点，如果map[cnt]=true说明就是交点

思路2：

1.统计A的长和B的长，谁长谁先走几步，走到长度一致位置
2.A和B一起走，遇到相同的节点返回即可
3.如果不相交，返回nil

思路3：

1.设链表A的不相交长为m，B不相交从部分为n，相交长为c，即len(A)=m+c,len（B）=n+c
2.循环，A和B一起走，如果A走到nil了，则A赋值为B的头，如果B走到nil了，则B赋值为A的nil
3.则A走了m+c+n,B走了n+c+m
4.m+c+n即走完了一遍A，并且走完了B的不相交部分，刚好停在了相交节点
5.而如果不相交，就是nil了

代码

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	mp := make(map[*ListNode]bool)
	cur := headA
	for cur != nil {
		mp[cur] = true
		cur = cur.Next
	}
	for headB != nil {
		if mp[headB] {
			return headB
		}
		headB = headB.Next
	}
	return nil
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	lenA := getLength(headA)
	lenB := getLength(headB)
	if lenA > lenB {
		cnt := lenA - lenB
		for i := 0; i < cnt; i++ {
			headA = headA.Next
		}
	} else {
		cnt := lenB - lenA
		for i := 0; i < cnt; i++ {
			headB = headB.Next
		}
	}
	for headA != nil && headB != nil {
		if headA == headB {
			return headB
		}
		headA = headA.Next
		headB = headB.Next

	}
	return nil
}
func getLength(root *ListNode) int {
	ans := 0
	for root != nil {
		ans++
		root = root.Next
	}
	return ans
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	curA, curB := headA, headB
	for curA != curB {
		if curA != nil {
			curA = curA.Next
		} else {
			curA = headB
		}
		if curB != nil {
			curB = curB.Next
		} else {
			curB = headA
		}
	}
	return curA
}