@R星校长
已知两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
杰哥我用白话翻译过来：
链表A和链表B相交于C节点，我们返回C节点的地址，如果两个链表之间没有交点，程序返回null
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
杰哥我用白话翻译过来：
不能删除节点、添加节点或是改变节点内的数据。
本题当中有多种解法，实现算法的时候，我们应该尽量使算法的时间复杂度为O ( n ) O(n)O(n)
，空间复杂度为O ( 1 ) O(1)O(1)
我们来看一个例子：
示例 1：
输入： intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出： Intersected at '8'
解释： 相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
杰哥我用白话翻译过来：
链表 A为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5] ，两个链表此时相交于值为8的节点，我们应将该节点的地址返回
/**
* Definition for singly-linked list.
* struct ListNode {
* int val; //节点中存储的数据
* ListNode *next; //指向下一个节点的指针
* ListNode(int x) : val(x), next(NULL) {} //构造函数
* };
*/
题目中ListNode代表链表中的一个节点，val是节点中存储的数据，next是指向下一个节点的指针。
构造函数ListNode初始化val的值为X，next赋为空。
我们需要开发求两个链表交点的函数getIntersectionNode
函数传入两个链表的头节点指针headA与headB。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB){
}
};
如果两个链表有交点，那么函数返回相交节点的地址，否则返回NULL。
杰哥带你分析题目：
首先可以想到两层循环来直接求解该题问题，用headA遍历链表A，对A当中的每一个节点，使用headB遍历B中的每一个节点，并同时检查headB是否与headA相同，如果相同，说明找到了两个链表的的交点。
例如，最初headA指向A的第一个节点，通过headB遍历B中的节点时候并没有发现地址与headA相同的节点，然后我们向后移动headA在链表B中，同样没有找到地址相同的节点，当headA指向第3个节点的时候，使用headB遍历链表B当中的节点,找到了与headA地址相同的节点，也就是两链表的交点，此时将它返回即可。
如果两个链表没有交点，那么最终headA与headB均会指向NUll，程序返回NULL。
假设链表A、B长度为n，该方法的时间复杂度为O ( n 2 ) O(n^2)O(n2)，并不是理想的方法，我们再介绍两种更优的算法。
第一种方法，通过STL中的set来优化搜索相同地址的过程，首先构建一个空的set，然后遍历链表A，再遍历链表B，将B中每个节点的地址在set中进行查询
当遇到第一个set中已出现的地址时，也就是说找到了两个链表的交点，否则说两个链表没有交点。
例如，遍历至节点8时，发现它的地址0x00C已经在set中出现，那么该节点为两个链表的交点，我们将它的地址返回。
如果说遍历了链表B中的全部节点，没有找到set当中出现过的地址，那么就说明链表中没有环
#include<stdio.h>
#include<set> //set容器的头文件
int main(){
std:set<int> check_set; //利用STL set找出数组a与b中重复出现的元素
int a[] = {4,1,8,4,5};
int b[] = {5,0,1,8,4,5};
for(int i = 0; i < 5; i++){ //遍历数组a
check_set.insert(a[i]); //将a中的元素添加至check_set
}
for(int i = 0; i < 6; i++){ //遍历数组b
//检查b中的元素是否在check_set中出现
if(check_set.find(b[i]) != check_set.end()){
//如果check_set中出现过该元素，则将它打印至屏幕
printf("已出现的元素：%d/n", b[i]);
}
}
return 0;
}
在正式讲解题目的代码之前，我们先来看一下set容器的使用。
样例代码利用STL set找出数组a与b中重复出现的元素，首先需要 #include <set> 引用set类的头文件，在main函数中，创建并命名为check_set的set，和数组a、b。
首先遍历数组a，将a中的元素添加至check_set，然后遍历数组b，检查b中的元素是否在check_set中出现，如果check_set中出现过该元素，则将它打印至屏幕，最终我们得到a与b中同时出现的元素为5、1、8、4、5
然后我们来讲解该方法的代码实现
using namespace std;
class Solution{
public
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB){
set<ListNode*> check_set; //判断相同节点的的集合
ListNode *result = NULL； //存储两链表的交点
while(headA){ //遍历链表A
check_set.insert(headA); //将链表A中的节点地址添加至check_set
headA = headA->next;
}
while(headB){ //遍历链表B
if(check_set.find(headB) != check_set.end()){ //找到了重复的节点
result = headB; //第一个重复的节点即为链表相交的交点，将它存储至result
break; //跳出循环
}
headB = headB->next;
}
return result; //函数返回result
}
};
首先，设置用来判断相同节点的集合check_set，指针result储存两链表的交点，初始化为NULL，使用while循环遍历链表A，将A中的节点地址添加至check_set，然后遍历链表b。
通过代码check_set.find(headB) != check_set.end()，判断节点是否在check_set出现，如果if条件成立，说明找到了重复的节点，而第一个重复的节点即为链表相交的交点，那么我们将它存储至result，跳出循环，最终函数返回result，至此，方法1中的思路与实现就讲完了
利用set来判断重复的地址时，由于set利用红黑树实现，在set集合中查找与添加一个元素的时间复杂度为O ( l o g N ) O(logN)O(logN)，所以算法的整体时间复杂度是O ( N l o g N ) O(NlogN)O(NlogN)，由于我们要把所有的地址都通过set存储，所以说空间复杂度为O ( N ) O(N)O(N)
下面我们会介绍双指针及算法，使得时间复杂度优化为O ( n ) O(n)O(n)，空间复杂度优化为O ( 1 ) O(1)O(1)
我们发现，在两个链表相交之后，有一段共享的链表，并且长链表比短链表多出一些结点。在找相交节点的时候，我们可以首先排除掉长链表多出的结点，这个时候两个链表的长度就相同了，然后我们再通过两个指针，同时用相同的速度扫描两个链表，当找到同一个链表时即为两个链表的交点了。
具体来说，首先通过指针遍历链表，计算链表A和链表B的长度，相减得出较长的链表多出的节点个数count——链表A - 链表B = count
例如，链表A的长度为5，链表B的长度为6，链表B比链表A多出了1个结点，然后将较长的链表的头节点指针向前移动count个结点，也就是将较长链表指针移动到，和较短表头节点对其的位置。
例如，计算出长链表比短链表多出1个节点，所以我们将headB向后移动1个节点，最后将headA与headB同时向前移动，当两个指针指向同一个节时，我们就找到了两个节点的相交结点地址返回，如果没有交点则返回NULL。
例如，当headA与headB移动到结点8时，两个指针值相同，即找到了两个俩链表的相交结点，即找到了两个链表的相交结点。，那么我们将该地址返回。
int list_length(ListNode *head){ //待求长度的链表头节点指针
int lenght = 0;
while(head){
lenght++;
head = head->next;
}
return length;
}
首先开发计算链表的长度list_length函数，函数参数为待求长度的的链表头节点指针head，设置length存储链表长度，通过while循环，每遍历一个节点，length++，最后函数返回链表的长度length，然后开发、移动较长链表头结点指针的函数move_pointer，函数传入链表头结点指针head与移动的节点数count，通过for循环，将head指针向前移动count个节点，函数返回移动后的指针head
ListNode *move_pointer(ListNode *head, int count){
//链表头结点指针head与移动的节点数count
for (int i = 0; i < count; I++){
//将head指针向前移动count个节点
head = head->next;
}
return head; //返回移动后的指针head
}
最后我们来看getIntersectionNode主体代码的开发
class Solution{
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB){
int lengthA = list_length(headA); //计算链表A的长度
int lengthB = list_length(headB); //计算链表B的长度
if(lengthA > lengthB){ //比较lengthA与lengthB的大小
//移动较长链表headA，使指针headA与headB对齐
headA = move_pointer(headA, lengthA - lengthB);
}
else{ //移动较长链表headB，使指针headB与headA对齐
headB = move_pointer(headB, lengthB - lengthA);
}
ListNode *result = NULL; //存储交点地址
while(headA && headB){ //同时向前移动headA与headB
if(headA == headB){ //当headA与headB相等时
result = headA; //该节点即为两链表的交点，将它的地址存储至result
break; //跳出循环
}
headA = headA->next;
headB = headB->next;
}
return result; //返回result，两个链表的交点地址
最后我们开发main函数测试程序接口。
int main(){
ListNode a(4);
ListNode b(1);
ListNode c(5);
ListNode d(0);
ListNode e(1);
ListNode f(8);
ListNode g(4);
ListNode h(5);
a.next = &b;
a.next = &f;
a.next = &d;
a.next = &e;
a.next = &f;
a.next = &g;
a.next = &h;
Solution solution;
ListNode *result = solve.getIntersectionNode(&a, &c); //求出两链表的交点地址
printf("%d\n" result->val);
return 0;
}
