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 }
