两个单链表相交，找出第一个交点
题目
给两个单链表，如何判断两个单链表是否相交？若相交，则找出第一个相交的节点
理解
解这道题之前，我们需要首先明确一个概念：
如果两个单链表有共同的节点，那么从第一个共同节点开始，后面的节点都会重叠，直到链表结束
因为两个链表中有一个共同节点，则这个节点里的指针域指向的下一个节点地址一样，所以下一个节点也会相交，依次类推。所以，若相交，则两个链表呈“Y”字形。如下图：
解法
暴力解法
从头开始遍历第一个链表，遍历第一个链表的每个节点时，同时从头到尾遍历第二个链表，看是否有相同的节点，第一次找到相同的节点即第一个交点。若第一个链表遍历结束后，还未找到相同的节点，即不存在交点。时间复杂度为O(n^2)。
使用栈
从头遍历两个链表。创建两个栈，第一个栈存储第一个链表的节点，第二个栈存储第二个链表的节点。每遍历到一个节点时，就将该节点入栈。两个链表都入栈结束后。则通过top判断栈顶的节点是否相等即可判断两个单链表是否相交。因为我们知道，若两个链表相交，则从第一个相交节点开始，后面的节点都相交。
若两链表相交，则循环出栈，直到遇到两个出栈的节点不相同，则这个节点的后一个节点就是第一个相交的节点。
// 单链表l1
LinkedList<String> l1 = new LinkedList<>();
l1.add("a");
l1.add("b");
l1.add("c");
l1.add("d");
l1.add("e");
l1.add("f");
// 单链表l2
LinkedList<String> l2 = new LinkedList<>();
l2.add("c1");
l2.add("d1");
l2.add("e");
l2.add("f");
/* 栈特性：后进先出 */
// 将l1元素压入s1栈中
Stack s1 = new Stack();
s1.addAll(l1);
// 将l2元素压入s2栈中
Stack s2 = new Stack();
s2.addAll(l2);
String temp = null;
/* s3栈存放所有相交节点 */
Stack s3 = new Stack();
while (!s1.empty() && !s2.empty()) {
/* peek方法获取第一个元素 */
temp = (String) s1.peek();
/* pop方法出栈 */
if ((s1.pop()).equals(s2.pop())) {
s3.add(temp);
} else {
break;
}
}
if(!s3.empty()) {
System.out.println("两个单链表相交，且相交的第一个节点，值为：\t" + s3.peek());
System.out.println(s3);
}
遍历链表记录长度
同时遍历两个链表到尾部，同时记录两个链表的长度。若两个链表最后的一个节点相同，则两个链表相交。
有两个链表的长度后，我们就可以知道哪个链表长，设较长的链表长度为len1,短的链表长度为len2。
则先让较长的链表向后移动(len1-len2)个长度。然后开始从当前位置同时遍历两个链表，当遍历到的链表的节点相同时，则这个节点就是第一个相交的节点
// 单链表l1
LinkedList<String> l1 = new LinkedList<>();
l1.add("a");
l1.add("b");
l1.add("c");
l1.add("d");
l1.add("e");
l1.add("f");
// 单链表l2
LinkedList<String> l2 = new LinkedList<>();
l2.add("c1");
l2.add("d1");
l2.add("e");
l2.add("f");
int ls1 = l1.size();
int ls2 = l2.size();
/* 判断l1与l2是否相交 */
if(l1.get(ls1-1).equals(l2.get(ls2-1))) {
System.out.println("两个单链表相交");
}
/* 获取相交节点 */
List ret = new ArrayList();
for(int i=0; i<ls2; i++) {
if(l2.get(i).equals(l1.get(i + (ls1-ls2)))) {
ret.add(l2.get(i));
}
}
System.out.println("相交的第一个节点为：\t" + ret.get(0));