判断两个链表是否相交，并且返回相交的点
1.暴力法是
A链表和B链表 先遍历A的整个来判断是否有和B节点相同的节点 然后再依此找完整个B要是地址相同第一个节点就是要返回的，但是时间复杂度很不好O（n^2）
2.优化的方法
先看结尾是否相交了，交了就一定交了 没交就是真没交，然后再看长的链表与短的链表差值，再让长的链表先走差的步数，最后再让长的和短的链表一起走
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode *tailA=headA; struct ListNode *tailB=headB; int lenA=0; int lenB=0; while(tailA){ lenA++; tailA=tailA->next; //遍历两个链表AB，来检查是否有重合的点，要是没有就返回空 } while(tailB){ lenB++; tailB=tailB->next; } if(tailA!=tailB){ return NULL; } int n=abs(lenA-lenB); //A表与B表也就是长表和短表的差值，注意不一定谁长谁短 struct ListNode*longlist=headB; struct ListNode*shortlist=headA; if(lenA>lenB){ longlist=headA; shortlist=headB;} while(n--){ //让长链表先走之间差值 longlist=longlist->next; } while(longlist!=shortlist){ //一起走找其中交点 longlist=longlist->next; shortlist=shortlist->next; } return longlist; }
