有两个有意思的关于链表的问题，大家可以先思考一下，再看我的讲解，一定会觉得妙趣横生。
问题一：找到链表中环的入口结点
大家看到，这个链表的入口结点就是：y1。那么怎么找到这个y1呢？我先通俗地阐述，再给出C语言源代码。
图1
在图1中，设置两个指针，slow和fast，slow指针每次前进一步，fast指针每次前进两步。
当slow和fast指针进入环中，经过有限次迭代，它们必然在z1点相遇。
这时让slow重新指向头结点x1，然后slow和fast指针每次前进一个结点，则它们必然在y1相遇。返回指向y1的slow指针即可。
代码如下：
public ListNode EntryNodeOfLoop(ListNode pHead) {if (pHead == null || pHead.next == null)return null;ListNode slow = pHead, fast = pHead;do {fast = fast.next.next;slow = slow.next;} while (slow != fast);fast = pHead;while (slow != fast) {slow = slow.next;fast = fast.next;}return slow;}
问题二：两个链表的第一个公共结点
显然，这两个链表的第一个公共结点就是c1。
算法描述：先让l1指针指向a1结点，l2指针指向b1结点。l1和l2每次前进一步，l1先到达c3，l1返回到指向b1。接下来，l2到达c3，返回到指向a1。此时，l1指向b2结点，两个指针同步前进，同时到达c1，程序返回c1，算法结束。
代码如下：
public ListNode FirstCommonNode(ListNode pHead1, ListNode pHead2) {ListNode l1 = pHead1, l2 = pHead2;while (l1 != l2) {l1 = (l1 == null) ? pHead2 : l1.next;l2 = (l2 == null) ? pHead1 : l2.next;}return l1;}
欢迎留言区讨论。
注：凡属于本公众号内容，未经允许不得私自转载，否则将依法追究侵权责任。