题目描述
题目分析
我们先要搞清楚一个概念，单链表可以相交，但绝对不会交叉
原因如下：
单链表中，多个结点可以存一个结点的地址，但是一个结点不可能存多个结点的地址
因为每个结点只有一个next
所以链表的相交一定是Y字形的
这里我们要做的有两步：
- 判断是否相交
- 找交点
思路一
暴力求解：A链表的所有结点依次去B链表找一遍
注意：一定要用结点的地址去比对
思路二
判断相交：
分别找尾结点，尾结点地址相同就相交
找交点：
算出两个链表的长度，得出两个链表的长度差，让长链表先走差距步，然后同时走，当第一个地址相同的时候，这就是交点
这个算法的时间复杂度是F(3N)，即O(N)
完整算法：
我们先定义curA，curB分别指向两个链表，用while循环求长度，并判断是否相交（只有相交了才会有交点）如果不相交则返回NULL，相交再进行下一步
我们得到lenA和lenB，用C语言自带的函数abs求出差距的绝对值
int n=abs(lenA-lenB);
那么谁先走呢，我们用假设法：假设A长B短
如果假设错误，那就纠正过来
让长的先走差距步
然后同时走，想等的时候返回任意一个地址就是交点
代码示例
根据思路二，我们写出代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode *curA=headA,* curB=headB; int lenA=1,lenB=1; while(curA->next) { lenA++; curA=curA->next; } while(curB->next) { lenB++; curB=curB->next; } if(curA!=curB) { return NULL; } int n=abs(lenA-lenB); struct ListNode *longList=headA, *shortList=headB; if(lenB>lenA) { longList=headB; shortList=headA; } while(n--) { longList=longList->next; } while(longList!=shortList) { longList=longList->next; shortList=shortList->next; } return longList; }
结果就可以通过了
