题目链接
题意
中文题，不过该题不是官方提供，所以不支持在LeetCode上设置数据跑，所以连自己测都不行，比acm刺激多了（手动滑稽）。
这个题就是给两个链表头，判定这两个链表是否相交。并且返回相交点的节点对象。
题解
据说是面试经典链表题了，这个题如果添加一个前置条件：两个链表的长度一定相等。瞬间就简单了许多：直接遍历俩链表，如果某个结点一样，就是相交结点了，输出就行。
而题目没有这个条件，那么我们手动处理一下就可以了，把比较长的链表多出来的部分截取就可以了，并且绝对不会从最后截（因为后部分是合并部分）。并且如果合并绝对不会再分开（突然脑洞想起来一下，太蛋疼了不存在的）。
那么我们先遍历一趟两个链表，并且统计长度，求差以后，对相对较长的链表先遍历，将多余的部分给过滤掉，然后就按照长度相等的两个链表来分析了。
这里有一些剪枝的方法：在第一次遍历长度的时候，如果最后一个节点是不相等的，那么一定不相交。如果其中有一个链表头为空，也绝对不相交（因为只有一个链表）。
另外，不用考虑两个链表相等的情况，如果求差是0，那么过滤的时候就等于一个节点就没过滤掉，所以不用单独判定相等。
AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int len1 = 1;
int len2 = 1;
ListNode initA = headA;
ListNode initB = headB;
if(headA == null || headB == null) return null;
while(headA.next != null){
len1++;
headA = headA.next;
}
while(headB.next != null){
len2++;
headB = headB.next;
}
if(headA != headB) return null;
headA = initA;
headB = initB;
int mul = Math.abs(len1 - len2);
if(len1 > len2){
while(mul-- != 0){
headA = headA.next;
}
}else{
while(mul-- != 0){
headB = headB.next;
}
}
while(headA != headB){
headA = headA.next;
headB = headB.next;
}
return headA;
}
}