这是悦乐书的第178次更新，第180篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第37题（顺位题号是160）。编写程序以找到两个单链表交叉的节点。例如：
以下两个链表：
A： a1→a2
↘
c1→c2→c3
↗
B：b1→b2→b3
链表A和链表B在c1处相交。
注意：
如果两个链接列表根本没有交集，则返回null。
函数返回后，链接列表必须保留其原始结构。
可以假设整个链接结构中没有任何环。
代码最好在O（n）时间内运行，并且只使用O（1）内存。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
这两个单链表，也可以看做是两数组，找出其中重复元素开始位置的值，最直接的办法就是上两层循环，外层遍历链表A，内层循环遍历链表B，直到遇到相交的节点为止，否则返回空。
特殊情况：当两链表中有一个为空的话，直接返回空。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode B = headB;
while (headA != null) {
while (headB != null) {
if (headA == headB) {
return headA;
}
headB = headB.next;
}
headA = headA.next;
headB = B;
}
return null;
}
但是此种解法的时间时间复杂度是O(n^2)，最坏的情况是两链表的长度都是n，并且相交的节点在最后位置或者没有相交的点。
03 第二种解法
先来看个例子，假设A和B两人要比武，A的功夫等级是10级，B的功夫等级是8级，B觉得这样比武不公平，就让A把实力压制到8级，再去和B比武，此时两人的功夫等级都是8级，于是开始了一场惊天动地的比武...
回到此题中来，因为无法确定两个链表的长度是否相等，就算两者有交点，但是起点不一样，还是会错过，无法找到交点。这时，我们就需要判断两链表的长度，重新定义好起点，才能开始遍历节点。
如果链表A长度大于链表B的长度，此时链表A就需要先向前移动两者之间长度差值个节点，然后才能和B开始依次遍历比较，反之B也是如此。
public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
int len1 = findLength(headA);
int len2 = findLength(headB);
int diff = (len1 >= len2) ? (len1 - len2) : (len2 - len1);
if (len1 >= len2) {
while (diff > 0) {
headA = headA.next;
diff--;
}
} else {
while (diff > 0) {
headB = headB.next;
diff--;
}
}
while (headA != null || headB != null) {
if (headA == headB) {
return headA;
}
headA = headA.next;
headB = headB.next;
}
return null;
}
public int findLength(ListNode head) {
int len = 0;
while (head != null) {
len += 1;
head = head.next;
}
return len;
}
04 第三种解法
还记得之前那道判断单链表是否有环的题目吗？没错，此题我们也可以借助环的思路来解题。
当遍历A链表时，如果遍历到了最后一位节点，此时跳转到B链表的起始节点，然后开始遍历B链表；当遍历B链表时，如果遍历到了最后一位节点，此时跳转到A链表的起始节点，然后开始遍历A链表。此时就相当于在遍历一条由链表A和链表B组合起来的新链表，如果此新链表存在环，那么表示两链表是有交点的，如果遍历完都没有碰到环，说明两链表是没有交点的。
public ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode A = headA;
ListNode B = headB;
while (A != B) {
if (A != null) {
A = A.next;
} else {
A = headB;
}
if (B != null) {
B = B.next;
} else {
B = headA;
}
}
return A;
}
05 小结
此题最优解法是第三种解法，其次是第二种，最差的解法是第一种。
算法专题目前已连续日更超过一个月，算法题文章37+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！