当前位置 博文首页 > 阳阳的博客：【leetcode.160】相交链表，很有意思的一道题
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
它们在节点c1相交，则返回节点c1。
注意：
最暴力的想法，就是分别遍历两条链，将节点存入集合中。之后使用两层for循环，判断是否在到达尾节点前存在相同的节点。时间复杂度为O(n2)，空间复杂度为O(n)。
当然，也有巧妙的方法：
首先使得pA指向A链的头节点，pB指向B链的头结点，他们每次的步伐一致。当pA到达A链尾部时，则下一步从B链头节点处继续向下遍历；当pB到达B链尾部时，则下一步从A链头节点处继续向下遍历。
如果两条链表相交，则在某个时刻，pA与pB会相遇。
以下是示意图，来自王小二的题解：
相当于，pA走过的路程为A链+B链，pB走过的路程为B链+A链，且它们的步伐一致，因此它们最后会在尾部相遇。如果两条链表相交，则他们会提前相遇。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode pA = headA, pB = headB;
//第一种情况,pA!=pB,说明没相遇,则继续往下走
//第二种情况,pA==pB,且它们都不为null,则说明相交，交点即为pA
//第三种情况,pA==pB,且它们都为null,则说明在尾部相遇,没有交点,返回pA,此时pA也为null
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}最后引用题解评论下方比较有趣的一句话，加深对这道题的印象：
cs走到尽头见不到你，于是走过你来时的路，等到相遇时才发现，你也走过我来时的路。
