leetcode:
https://leetcode.cn/problems/intersection-of-two-linked-lists...
解题思路:
双指针 如果链表A和链表B长度别离为a和b, 如果两个链表相交,那么公共局部的长度必定是相等的,假如为c, 那么链表A在公共局部前的长度就是a-c, 同理链表B在公共局部前的长度就是b-c, 于是就有了a+b-c = b+a-c, 也就是说如果l1,l2两个指针别离指向链表A和链表B的头结点,而后同时同速的向右挪动,如果挪动到空节点,则转移到对方的头结点继续移动,它们俩肯定会在相交处相遇。它们俩的静止轨迹正好就是a+b-c = b+a-c, 如果它们没有相交,那么它们肯定会在某个时刻同时挪动到空节点(nil),此时返回空节点(nil)即可。
func getIntersectionNode(headA, headB *ListNode) *ListNode { curA,curB := headA,headB for curA != curB { if curA == nil { // 如果第一次遍历到链表尾部,就指向另一个链表的头部,持续遍历,这样会对消长度差。如果没有相交,因为遍历长度相等,最初会是 nil == nil curA = headB } else { curA = curA.Next } if curB == nil { curB = headA } else { curB = curB.Next } } return curA}