题目中没有说有环还是无环,所以有了下面一大堆长的代码。思路在注释中。
public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { // 处理空的情况 if (pHead1 == null || pHead2 == null) { return null; } // 判断是否有环,并且返回环的入口地址 ListNode loop1 = EntryNodeOfLoop(pHead1); ListNode loop2 = EntryNodeOfLoop(pHead2); // 必须都有环或者无环 // 若一个有环,另一个无环,则返回 null if (loop1 == null ^ loop2 == null) { return null; } // 三种情况:1. 同一个入口 2. 不同入口 3. 完全是两个环 // case 1 同一个入口地址,将入口作为结尾,计算无环情况 if (loop1 == loop2) { return FirstCommonNodeBeforeLoop(pHead1, pHead2, loop1); } // case 2 不同入口,其中一个增加,必然在某个位置相交 // 如果循环一圈之后还不相交,说明是 case 3 ListNode tempNode = loop1; do{ tempNode = tempNode.next; if(tempNode == loop2) { return loop1; } } while(tempNode != loop1); return null; } public static ListNode FirstCommonNodeBeforeLoop(ListNode pHead1, ListNode pHead2, ListNode endNode) { ListNode curNode1 = pHead1; ListNode curNode2 = pHead2; // 算 pHead1 长度 int len1 = 0; while (curNode1 != endNode) { len1++; curNode1 = curNode1.next; } // 算 pHead2 长度 int len2 = 0; while (curNode2 != endNode) { len2++; curNode2 = curNode2.next; } // 快慢指针法 curNode1 = pHead1; curNode2 = pHead2; if (len1 >= len2) { for (int i = 0; i < len1 - len2; i++) { curNode1 = curNode1.next; } } else { for (int i = 0; i < len2 - len1; i++) { curNode2 = curNode2.next; } } while (curNode1 != curNode2) { curNode1 = curNode1.next; curNode2 = curNode2.next; } return curNode1; } public static ListNode EntryNodeOfLoop(ListNode pHead) { ListNode fastPointer = pHead; ListNode slowPointer = pHead; do { if (fastPointer.next == null || fastPointer.next.next == null) { return null; } // 快慢指针法 fastPointer = fastPointer.next.next; slowPointer = slowPointer.next; } while (fastPointer != slowPointer); // 寻找交点 fastPointer = pHead; while (fastPointer != slowPointer) { fastPointer = fastPointer.next; slowPointer = slowPointer.next; } return fastPointer; } }