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
}