前言：

本链接：力扣

目录

前言：

一. 题目分析：

二. 思路的走向

三. 代码的书写

---

一. 题目分析：

至此，此题就会有两大类情况：

1. 两链表是相交链表，那么就代表从相交的起始节点起，后面的节点必定都会是重叠的，直到链表结束，（单链表的节点只具有一个指针，这代表其能被多个指针所指，但其本身只能指向一个方向）
2. 两链表不是相交链表，二者没有相同地址的的节点。

（二者最大的区别就是：相交则两个链表的最后一个节点必点相等（NULL除外），不相交则必定是不相等）(留作一个突破口)

二. 思路的走向

既然要找到相交点，那么进行 == 比较就是必要的了。但是我们无法知晓其相交起始点的位置。那么，就需要一个链表逐一向后的同时与另一个链表的除NULL外的节点地址遍历：

这个方法是暴力解题法，时间复杂度为：O(n^2)。如果这只是通过的话，那是没有问题的，但是如果对于其的进阶要求，这时间复杂度就远远的过了：

  时间复杂度为O(m+n),证明两链表的遍历最好是一一对应，这样才会是一次方的m或n。

随之，通过画图可以发现：

  所以，只需分别遍两个链表，计算二者分别的长度，来得到二者相差的长度。这正好也就分别可以得到两个链表的最后一个节点，可以，以此判断其是否是相交的。可以大大的提高对于是否为相交链表的判断，而且对于此只判断是否为相交链表的算法，时间复杂度为：O(m+n)。

再看看相交起始点的判断，我们是一一对应的比较，时间复杂度就是长度，既是O(m)或O(n),无非就是短的那条链表的长度。

在此空间的使用，的大量使用是没有的，只有个位的空间使用。即空间复杂度为：O(1)。

整体空间复杂度为：O(m+n)。

---

再思考，此题会出现几种特例，看是否有许注意的点：

特例一与特例三是最为普通的两种状态，也是我们前面所考虑到的。而特例二就是一个我们需要注意的特例。我们是需要进行,例如：head->next 的使用，如果我们忽视此特例，就会出现野指针的问题。

同时我们可以发现，这其实只需写 if(……)  return NULL; 即可，于是我们可以将其放在最前面，可以提高代码在此类特例的运行速度。

三. 代码的书写

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
	//防止其中一个链表为空
	if(NULL == headA)
		return NULL;
	if(NULL == headB)
		return NULL;

	//分别遍历，计算二者各自的长度
    int lenA =0,lenB = 0;
    struct ListNode* curA,* curB;
    curA = headA,curB = headB;
    lenA = 1;
    while(curA->next)
    {
        curA = curA->next;
        lenA++;
    }

    lenB = 1;
    while(curB->next)
    {
        curB = curB->next;
        lenB++;
    }

	//判断最后一个节点是否相等（是否相交）
    if(curA != curB)
        return NULL;

	//将二者长度变为一样
    struct ListNode* longheadA,* shortheadB;
    longheadA = headA;
    shortheadB = headB;

    if(lenA < lenB)
    {
        longheadA = headB;
        shortheadB = headA;
    }
    int gap = abs(lenA - lenB);
    while(gap--)
    {
        longheadA = longheadA->next;
    }

	//一一对应比较，判断重叠节点(因为前面已经经过是否相交的判断，所以执行至此，必定是相交的)
    while(longheadA != shortheadB)
    {
        longheadA = longheadA->next;
        shortheadB = shortheadB->next;
    }

	//二者相等，任意一一个都是相交起始点
    return longheadA;
}