题目背景

这是一道来自微软亚洲研究院的编程面试题，属于链表系列中的第 7 题。

题目描述

给出两个单向链表的头指针，例如 h1 和 h2，判断这两个链表是否相交。

为了简化问题，这里假设两个链表都不带环。

解题思路

判断两个链表是否相交，本质上就是看它们是否存在地址相同的节点。只要能找到地址相等的节点，就说明两条链表在某个位置汇合到了一起。

基于这个观察，可以采用下面的做法：

  • 先扫描其中一条链表一次，把每个节点的地址取出来，转换为 int 存入一个 vector。
  • 再遍历另一条链表，对每个节点的地址依次调用 find，看它是否出现在之前收集的地址集合里。
  • 只要命中任意一次，就说明两条链表相交；如果全部扫描完都没命中，则说明两条链表不相交。

参考代码片段

/*by hk 15-7-1*/

判断是否相交也就是说 节点地址是否相等，
可以先扫描一次，吧地址读出来 转换为int 存入vector 然后依次 调用find

.