编写程序以查找两个单链表的交点开始的节点。如图8-4所示,以下两个链表,交点开始的节点是c1。
图8-4 两个链表的交集
思路:可以利用哈希表,把其中一个链表的所有节点保存下来。然后遍历另外一个链表,如果在哈希表中找到相同的节点,则返回。示例代码如下。
代码清单8-2 利用哈希表寻找链表的交集
当然,还有一个思路,就是双指针操作,确保两个链表具有相同的长度,然后遍历,寻找是否具有相同节点。示例代码如下。
代码清单8-3 利用双指针寻找链表的交集 WnmVdQ6Qx/zHFi88SwHqKLuId0i8Ho0IPI75MoSpdKhHmUUqO2anRA2MgtHBkIKV