两个链表的第一个公共结点

数据结构和算法

蛮力法

第一个链表(长度为m)遍历一个结点，第二个链表(长度为n)遍历每个节点，如果出现一样的，则说明重合,时间复杂度是O(mn)

利用栈

从链表的最后结点开始遍历，但是单向链表只能从头到尾，利用后进先出，
可以分别将两个链表的结点放入栈中，这样两个链表的尾结点就在两个栈的栈顶，同时弹出栈顶，知道找到相同的结点
空间复杂度是O(m+n)。时间复杂度也是O(m+n)
用空间换取时间

较长链表先走

之所以用栈，是想同时遍历两个栈的尾结点。当两个链表长度不一致时，从头开始遍历到尾结点的时间就不一致

看两个链表的长度哪个长，长比短的多几个结点，第二次遍历时，较长的链表先走若干部，接着再同时在俩个链表上遍历，找到的第一个相同结点就是他们的公共结点

时间复杂度为O(m+n)，省下了辅助的栈，提高空间效率