链表相交在数据结构和算法之间，找到交点

链表相交链接链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci给你两个单链lists对于头节点headA和headB，请找到并返回两个单向链表相交的起始节点。如果两个链表不相交，则返回null。如图所示，两个链表相交于节点c1：标题数据保证整个链表结构无环。注意链表在函数返回结果后必须保持原来的结构。例1：例2：例3：思路很简单，就是求两个链表交集结点的指针。这里同学们要注意，交点不是数值相等，而是指针相等。为了举例方便，假设节点元素的值相等，则节点指针相等。看下面两个链表。目前curA指向链表A的头节点，curB指向链表B的头节点：我们求两个链表的长度，求两个链表长度的差，以及然后让curA移动到，和curB的末端对齐的位置，如图：此时，我们可以比较curA和curB是否相同。如果不是，则同时向后移动curA和curB。如果curA==curB，找到交点。否则循环通过返回空指针退出。C++代码如下：classSolution{public:ListNode*getIntersectionNode(ListNode*headA,ListNode*headB){ListNode*curA=headA;ListNode*curB=headB;intlenA=0,lenB=0;while(curA!=NULL){//求链表A的长度lenA++;curA=curA->next;}while(curB!=NULL){//求链表B的长度lenB++;curB=curB->next;}curA=headA;curB=headB;//设curA为最长链表的头部，lenA为其长度if(lenB>lenA){swap(lenA,lenB);swap(curA,curB);}//求长度differenceintgap=lenA-lenB;//让curA和curB在同一个起点（结束位置对齐）while(gap--){curA=curA->next;}//遍历curA和curB，如果它们一样的，直接returnwhile(curA!=NULL){if(curA==curB){returncurA;}curA=curA->next;curB=curB->next;}returnNULL;}};时间复杂度：空间复杂度：其他语言版本JavapublicclassSolution{publicListNodegetIntersectionNode(ListNodeheadA,ListNodeheadB){ListNodecurA=headA;ListNodecurB=headB;intlenA=0,lenB=0;while(curA!=null){//求链表长度AlenA++;curA=curA.next;}while(curB!=null){//求链表B的长度lenB++;curB=curB.next;}curA=headA;curB=headB;//设curA为最长链表的头部，lenA是它的长度if(lenB>lenA){//1.swap(lenA,lenB);inttmpLen=lenA;lenA=lenB;lenB=tmpLen;//2.swap(curA,curB);ListNodetmpNode=curA;curA=curB;curB=tmpNode;}//求长度差intgap=lenA-lenB;//让curA和curB在同一起点（结束位置对齐）while(gap-->0){curA=curA.next;}//遍历curA和curB，遇到相同直接返回while(curA!=null){if(curA==curB){returncurA;}curA=curA.next;curB=curB.next;}returnnull;}}PythonclassSolution:defgetIntersectionNode(self,headA:ListNode,headB:ListNode)->ListNode:"""按照速度的规律，快的赶上慢的。在这道题，有的链表简而言之，他走完了会去另一个链表，我们可以理解为一个快速移动的指针，那么只要其中一个链表走完了，他就会去另一个链表链表。如果有交集，最终会在同一个位置相遇"""cur_a,cur_b=headA,headB#用两个指针替换a和bwhilecur_a!=cur_b:cur_a=cur_a.nextifcur_aelseheadB#如果a完成，则switchGotobgocur_b=cur_b.nextifcur_belseheadA#同理，switchtoareturncur_aGofuncgetIntersectionNode(headA,headB*ListNode)*ListNode{curA:=headAcurB:=headBlenA,lenB:=0,0//求A,B的LengthforcurA!=nil{curA=curA.NextlenA++}forcurB!=nil{curB=curB.NextlenB++}varstepintvarfast,slow*ListNode//请求长度差，让较长的链表按长度差先走iflenA>lenB{step=lenA-lenBfast,slow=headA,headB}else{step=lenB-lenAfast,slow=headB,headA}fori:=0;i0){curA=curA.next}while(curA&&curA!==curB){curA=curA.next;curB=curB.next;}returncurA;};