一、题目：
1.(相交链表)(只能聚合，不能发散，Y字形，不是X字形)
给你两个单链表的头结点headA，headB，请你找出并返回相交单链表的起始结点，如果两个链表没有交点就返回NULL;
思路一：（暴力求解法）遍历A链表，依次取A链表中的每一个结点，依次跟B链表中的的所有结点比较，如果有地址相同的结点，就是相交，第一个相同的交点（前提是要让我的链表的长度保持一致）
思路二：优化从O（N^2）到 O（N）
1.尾结点相同就是相交，否则就是不想交（因为如果这个链表是一个有交点的链表，那么它的尾结点就一定是相交的，因为链表只能是Y 字形的结构，不是X字形的结构）
所以此时直接找尾，然后判一下就行了
2.求交点：此时就是想让这个代码是时间复杂度为O（2*N），就是双指针一起向后走（然后同一个位置的结点进行比较，如果相同就表示有交点）
但是这种原理的前提是两个链表要是相同的长度的，所以这变我们此时就要把链表的长度先给求出来（然后让更长的那个链表先走x步，走到最后跟较短的那个链表的长度一样，然后开始比较）
3.头结点就是头结点，不能乱给它移动位置，所以都是用一个cur去迭代找尾
1.故事理解代码：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { //你是一个农村出身的穷小伙，她是一个一线城市的富家女，你爱上了她，你们的故事就此开始... //如果你们两没有遇见对方，此生无缘 if (!headA || !headB) return NULL; int lengthA = 0; int lengthB = 0; struct ListNode *pA = headA; struct ListNode *pB = headB; //这是你目前的实力 while(pA->next != NULL){ pA = pA->next; lengthA++; } //这是她目前的实力 while(pB->next != NULL){ pB = pB->next; lengthB++; } //富家女的父亲和你谈话，摆明了你和她目前的差距是天与地，好让你认清现实，放弃他女儿 int mid = lengthA - lengthB; struct ListNode *ppA = headA; struct ListNode *ppB = headB; //但是你不肯放手，想要与命运搏一搏，所以日以继夜的充实自己，追赶者她的步伐 while (mid > 0){ ppA = ppA->next; mid--; } while (mid < 0){ ppB = ppB->next; mid++; } //你不断努力，终于把你和她之间的差距缩小到了最小 //然后你们领了证，开始了婚后的平淡生活 while( ppA != ppB){ //结局1 : 结婚后，诸多因素导致了你与她产生了嫌隙，最终，你们不欢而散 ppA = ppA->next; ppB = ppB->next; } return ppA; //结局2 : 一直到最后你们仍旧和以前一样相濡以沫，走完了这一生，恭喜! }
2.理论理解代码：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { //这个题目的重点就是如何理解交点：要明白交点就是在同一位置时相等的点叫交点，不是相等就是交点，一定要是同一个位置才算是交点，所以假如链表长度不同，怎么可能在多余的地方找到交点 struct ListNode *tailA=headA; struct ListNode *tailB=headB; //此时有了这两个尾指针我就要开始找尾了（然后进行尾的比较，如果尾的位置都不相同，那么就肯定不相交，因为根据图或者原理，可以知道只要这个是一个相交的链表那么尾肯定是相交的） //并且此时为了可以方便后面的计算，我们这边可以顺便把链表的长度给计算一下 int lenA=1; while(tailA) { lenA++; tailA=tailA->next; } int lenB=1; while(tailB) { lenB++; tailB=tailB->next; } if(tailA!=tailB) { return NULL; } int gab=abs(lenA-lenB);//这个位置也可以使用三目操作符 struct ListNode*longlist=headA; struct ListNode*shortlist=headB; if(lenA<lenB) { longlist=headB; shortlist=headA; } while(gab)//就是为了让我的末尾的位置对齐，才可以进行比较 { longlist=longlist->next; gab--; } //此时程序来到这个位置就是说明我的链表是一样长的了 while(longlist!=shortlist) { longlist=longlist->next; shortlist=shortlist->next; } //程序来到这个位置，自然而然的是说明我此时地址的位置相等，自然就是找到了相交的位置了 return longlist; }
