1.限制和要求
- 如果两个链表没有交叉返回NULL，有相交返回相交的点。
- 两个链表的原始结构不能被修改。
- 两个链表中都没有环。
- 算法的时间复杂度要求是O(n)，空间复杂度是O(1)。
2.思考
- 算法1
- 分别遍历两个链表，记录遍历的节点。
- 出现重复的节点，就说明两条链表相交。
- 第一个重复出现的节点就是交点。
- 算法2
算法1不能满足空间复杂为O(1)的要求，因为你需要记录遍历过的节点，认真分析后发现如果两个链表有相交那么它们的尾节点必定是相同的。
- 分别遍历两个链表，记录遍历的尾节点和链表长度，如果两个链表的尾节点相同则说明链表相交。
- 在两边相交的情况下，如果两个链表的长度不一致，则较长的链表先从链表头遍历n步，n为两个链表的长度差。
- 长度短的链表从链表头往后遍历，长度长的链表继续往后遍历，直到遍历到相同的节点，而这个节点就是这两个链表的交点。
3.算法图解
- 相交初始状态
相交初始状态
- 长链表先往后遍历n步
长链表先往后遍历n步
- 一直往后遍历直到遇到相同的节点
一起向后遍历1
一起向后遍历2
4.代码实现
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode * getIntersectionNode(ListNode * ahead, ListNode * bhead) {
int alen = 0;
int blen = 0;
ListNode * acur = ahead;
ListNode * bcur = bhead;
alen = 1;
while (acur && acur->next)
{
++alen;
acur = acur->next;
}
blen = 1;
while (bcur && bcur->next)
{
++blen;
bcur = bcur->next;
}
if (acur == bcur) //尾节点相同
{
acur = ahead;
bcur = bhead;
int n = abs(alen - blen);
if (alen > blen) //比较长的节点先往后遍历n步
while (n--) acur = acur->next;
else
while (n--) bcur = bcur->next;
while (acur != bcur) //一直往后遍历直到相交点
{
acur = acur->next;
bcur = bcur->next;
}
return acur;
}
else //没有相交
{
return NULL;
}
}
};
