# 1. 题目描述
给定两个可能相交的单链表，头结点`head`和`head2`，要求实现一个函数，如果两个链表相交返回相交的第一个节点，如果不相交，返回`null`。
要求：如果两个链表长度之和为`N`，时间复杂度为`O(N)`，额外空间复杂度为`O(1)`。
# 2. 解答
## 2.1 暴力
~~~
/**
* 解法一，使用额外空间，但是不满足题意
* @param listA 链表A
* @param listB 链表B
* @return 返回相交节点或者null
*/
public Node findPointNode(Node listA, Node listB){
if(listA == null || listB == null) return null;
Set<Node> sets = new HashSet<>();
Node ptr = listA;
while(ptr != null){
sets.add(ptr);
ptr = ptr.next;
}
ptr = listB;
while(ptr != null){
boolean contains = sets.contains(ptr);
if(contains) return ptr;
ptr = ptr.next;
}
return null;
}
~~~
## 2.2 遍历
对于单链表的相交问题，这里需要分情况讨论，比如下面的图示：
<img src="http://weizu_cool.gitee.io/gif-source/images/屏幕截图 2022-01-11 103719.png"/>
所以这里需要分情况讨论，也就是需要先看下这两个链表中是否有环的存在。对于两个无环的链表，我们直接遍历得到其长度，然后进行等长同步遍历即可。对于有环链表，可以采用类似的思想，区别之处在于对于有环的链表这里的长度判断为从头节点到环入口节点的长度。那么获取其有环或者无环链表长度的代码可以描述为：
~~~
/**
* 获取链表其长度
* @param list 待判断链表
*/
private int getListLength(Node list) {
if(list == null) return 0;
Node fast = list, slow = list;
boolean flag = false;
int length = 1;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
length++;
if(fast == slow){
flag = true;
break;
}
}
if(flag){ // 有环
fast = list;
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
slow = list;
int count = 0;
length = 0;
while(count < 2){
slow = slow.next;
if(slow == fast){
count++;
}
length++;
}
return length;
} else{ // 无环
return length * 2;
}
}
~~~
对应的，可以先判断这两个链表的长度，然后计算其差值，同步遍历即可获取其相交节点。
~~~
/**
* 解法二，综合处理获取链表长度，然后同步遍历即可
* @param listA 链表A
* @param listB 链表B
* @return 返回两个链表相交点的首节点
*/
public Node findPointNode_2(Node listA, Node listB) {
if (listA == null || listB == null) return null;
int lengthA = getListLength(listA);
int lengthB = getListLength(listB);
int diff = lengthA - lengthB;
Node tempA = listA;
Node tempB = listB;
if(diff < 0){
diff = diff * -1;
while(diff != 0){
tempB = tempB.next;
diff--;
}
} else if(diff > 0){
while(diff != 0){
tempA = tempA.next;
diff--;
}
}
while(tempA != tempB){
tempA = tempA.next;
tempB = tempB.next;
}
return tempA;
}
~~~
可以做一个简单的测试：
~~~
public static void main(String[] args) {
Node node_0 = new Node(8);
Node node_1 = new Node(5);
Node node_2 = new Node(3);
Node node_3 = new Node(5);
Node node_4 = new Node(7);
Node node_5 = new Node(8);
Node node_6 = new Node(9);
node_2.next = node_3;
node_3.next = node_4;
node_4.next = node_5;
node_5.next = node_6;
node_6.next = node_3;
node_0.next = node_1;
node_1.next = node_3;
int listLength_1 = new Intersect().getListLength(node_2);
System.out.println(listLength_1);
int listLength_2 = new Intersect().getListLength(node_0);
System.out.println(listLength_2);
Node pointNode_2 = new Intersect().findPointNode_2(node_0, node_2);
System.out.println(pointNode_2.val);
}
~~~
<img src="http://weizu_cool.gitee.io/gif-source/images/屏幕截图 2022-01-11 111148.png"/>
