本系列博客为个人刷题思路分享，有需要借鉴即可。
1.题目链接：
2.详解思路：
思路1：用尾结点是否一样来判断是否相交，用相对移位来找到结点
思路2：双层嵌套循环，时间复杂度O（N*N），分析代码略
//错误示例代码： /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ #include<math.h> struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { if(headA==NULL||headB==NULL)//错1：审题问题：题目中明确说没有空链表 { return NULL; } //判断是不是相交链表 struct ListNode* pTailA = headA; struct ListNode* pTailB = headB; int skipA = 0; int skipB = 0; //错2：细节问题：要想要统计结点个数，应该写作while(pTailA)这里最后一个结点没有统计上 while(pTailA->next) { pTailA=pTailA->next; skipA++; } while(pTailB->next) { pTailB=pTailB->next; skipB++; } //如果不是相交链表没必要找，直接跳出 if(pTailA!=pTailB) { return NULL; } //如果是，那么继续 int sub = abs(skipA-skipB); struct ListNode* pmin = NULL; struct ListNode* pmax = NULL; if(skipA<skipB) { pmin = headA; pmax = headB; } else { pmin = headB; pmax = headA; } while(sub--) { pmax = pmax->next; } //错3：逻辑全面问题：应该写成pmin!=pmax，这里这样写也会跑过一些代码，但是如果刚开始就是交点呢？ while(pmin->next!=pmax->next&&pmin->next&&pmax->next) { pmin = pmin->next; pmax = pmax->next; } return pmax->next; }
反例：
所以正确恰当的代码应该如下：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { //判断是不是相交链表 struct ListNode* pTailA = headA; struct ListNode* pTailB = headB; int skipA = 0;//统计A链表中结点的个数 int skipB = 0;//统计B链表中结点的个数 while(pTailA->next) { pTailA=pTailA->next; skipA++; } skipA++; while(pTailB->next) { pTailB=pTailB->next; skipB++; } skipB++; //不是交点 if(pTailA!=pTailB) { return NULL; } //如果是，那么继续 int sub = abs(skipA-skipB); struct ListNode* pmin = NULL; struct ListNode* pmax = NULL; if(skipA<skipB) { pmin = headA; pmax = headB; } else { pmin = headB; pmax = headA; } //让长的先走一些，让长短对齐 while(sub--) { pmax = pmax->next; } //找交点 while(pmin!=pmax) { pmin = pmin->next; pmax = pmax->next; } return pmax; }
完。
