【LeetCode】相交链表——面试经典题目
题目链接：力扣
首先先声明一下这里的相交可不是如下图一样的相交
这样相交是错误的，一个节点的指针域是不可能同时存放两份地址的。
这样的相交才是正确的
思路一：根据题目意思，我们要的是相交的起始节点，那么我们可以先遍历两个链表，得到这两个链表的长度，再用较长的链表减去较短的链表，得到一个差值（后面我就用gap来代替这个差值了），再让较长的链表先走gap步，走完后，较短的链表和较长的链表同时向后走，直到走到他们的下一个节点相等时停止，这一个节点就是它们的相交节点。
画图演示如下：
代码如下：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {//判断链表是否为空可加可不加if(headA==NULL||headB==NULL){return NULL;}struct ListNode* curA=headA;struct ListNode* curB=headB;int lenA=1,lenB=1;//计算链表的长度while(curA->next){ curA=curA->next; lenA++;}while(curB->next){ curB=curB->next; lenB++;}//没有节点则返回NULLif(curA!=curB){ return NULL;}//求第一个交点struct ListNode *shortlist=headA,*longlist=headB;//一个小技巧if(lenA>lenB){ shortlist=headB; longlist=headA;}//计算两个链表长的差值//用abs计算绝对值，就不用考虑顺序问题int gap=abs(lenA-lenB);//长的先走gap步while(gap--){ longlist=longlist->next;}//找相同节点while(shortlist!=longlist){ shortlist=shortlist->next; longlist=longlist->next;}//返回longlist也是一样的return shortlist;}思路二：定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差) 两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度。
class Solution {public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if(headA == NULL || headB == NULL) return NULL; ListNode*curA = headA, *curB = headB; // 在这里第一轮体现在curA和curB第一次到达尾部会移向另一链表的表头, 而第二轮体现在如果curA或curB相交就返回交点, 不相交最后就是null==null while(curA != curB) { curA = curA == NULL ? headB : curA->next; curB = curB == NULL ? headA : curB->next; } return curA; }};这个思路不太好想，知道有这个就行
总结：数据结构的oj题就是要多画图才能分析出来，光想的话还是有点难的。
今天的题解就分享到这
觉得内容对你用的话，就给博主三连哦！！！
