例题10：相交链表。

　　两个单向链表中的节点发生next指针指向同一节点的情况，称为两个链表相交，如下图所示。

　　相交链表在程序上要求：

　　（１）需要在链表类中声明一个能让两个链表形成交叉的cross方法，方法中需要实现下面２项功能：

　　A、设置本链表对另一链表的引用，和另一链表对本链表的引用。

　　B、新加入的节点需要被两个链表的尾节点next指针同时指向。

　　（２）已经设置相交后，在两个链表中任意一个中追加新的数据都将触发另一链表的长度增加。

　　为了实现这二个要求，新增一个能直接通过节点对象追加链表的私有方法（__appendNode）以供cross方法使用，同时也用它覆盖追加方法（append），使追加方法能触发另一链表的长度增加。

　　程序代码：

　　运行结果：

　　练习题１：创建二个单向链表，使他们相交于尾节点。
　　练习题２：如果采用头插法，如何构建两个相交单向链表。
　　练习题３：两个链表能否相交于头节点。

　　例题11：判断两个链表是否相交。

　　判断两个链表是否相交并找出交点。

　　算法分析如下：

　　(1)找相交：两个链表都用临时指针遍历到尾节点，如果两个链表的尾节点相同，则两个链表必然相交。

　　(2)找交点：两个链表长度相减，哪个链表长则链表的临时指针先移动过差值，然后两个链表指针一起移动，每移动一对节点比较一次，直到找到两个指针指向同一节点的情况。找相交和找交点的算法图解方式如下图所示。

　　程序代码：

　　运行结果：

　　练习４：如果把上一例题的测试代码改为下图所示，那么打印出来的是不是和原来的一样？

　　学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。更多课程请打开“学思营”同步网站：http://www.5xstar.com/doc.html

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社