链表如果相交,找到交点

问题

对于这样两个链表:

50

50

如何找到第一个交点 3 ?

分析

一种简单的解决思路是,把这个链表的尾节点和任意一个链表的头节点连起来:

50

可以是链表 1 的尾节点到链表 2 的头节点,或者链表 2 的尾节点到链表 2 的头节点,总之连起来以后,问题就转变成了,找到链表环的起点。