JZ52 两个链表的一个公共结点

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;
  }
}