单链表——相交链表
方法一
我们可以定义两个指针分别指向链表的头部，遍历链表A使A的每一个节点都与B的每一个节点比较，若地址相等，则返回指向A链表的指针，若不想等则将A指向A的下一个节点。这样可以得知，假设A链表的长度为N，B链表的长度为M，则该想法的时间复杂度为O(M*N)，可知，该想法效率较低。
方法二
我们可以先遍历两个链表。计算出两个链表的长度分别为多少，假设A链表的长度为N，B链表的长度为M，A链表比B链表短，则可以计算出AB链表相差M-N个节点。所以我们可以先将长链表的指针挪到与短链表同步的节点，然后两个指针同时进行，直到两个指针指向的地址相同时，再停止。由此可知，这个方法的时间复杂度为O(max(M,N))。那么我们现在来实现一下这个方法。
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{//首先判断两个链表是否有交点，并计算两个链表的长度ListNode*pcurA=headA;ListNode*pcurB=headB;int lenA=0;int lenB=0;while(pcurA){pcurA=pcurA->next;++lenA;}while(pcurB){pcurB=pcurB->next;++lenB;}//若尾节点地址不同，则两个链表不相交if(pcurA!=pcurB){return NULL;}//若相交，则找相交的节点，先将两个链表的指针都指向距离相交节点相同的位置，再同时走//使用假设法int gap=abs(lenA-lenB);ListNode*longList=headA;ListNode*shortList=headB;if(lenA<lenB){shortList=headA;longList=headB;}while(gap--){longList=longList->next;}while(longList!=shortList){longList=longList->next;shortList=shortList->next;}return shortList;
}
大家感兴趣的可以自行尝试哦~
. - 力扣（LeetCode）