剑指offer_23_链表中环的入口节点

• 2019 年 10 月 6 日
• 筆記

定义两个"指针"，这俩个"指针"一快一慢，比如说一个"指针"每次移动一步，而另一个"指针"每次移动俩步，如果这俩个指针相遇了，那么说明链表里存在环。

相遇了之后固定一个"指针"，让另一个"指针"每次移动一格，第二次相遇的时候记录另一个"指针"移动的步数，也就是环的大小了记为m步。

得到环的大小之后，我们只需要从链表头开始先让一个"指针"先移动m步，也就是环的大小，再让另一个"指针"从链表头开始移动，这样当俩个"指针"相遇的时候，就是链表中环的入口啦。代码如下：

// 链表中环的节点入口  public static ListNode findNode(ListNode node) {      if (node == null ) {          return null;      }      // 找到在环中相遇的节点      ListNode mettingNode = findMettingNode(node);      // 求取环的大小      int count = findCount(mettingNode);      // 求出环的开始节点      return findStartNode(node, count);  }    // 找到指针在链表相遇的节点  public static ListNode findMettingNode(ListNode node) {      ListNode fast = node;      ListNode slow = node;      if (node.next == null) {          return null;      }      while ((fast = fast.next) != null && (slow=slow.next.next) != null ) {          if (fast == slow) {              return fast;          }      }      return null;  }    // 求取链表中环的大小  public static int findCount(ListNode node) {      // 定义俩个"指针"      if (node == null) {          return 0;      }      ListNode move = node;      int count = 0;      while ((move = move.next) != null) {          count++;          if (move == node) {              return count;          }      }      return 0;  }  // 求环所在的节点  public static ListNode findStartNode(ListNode node,int count) {      if (count == 0) {          return null;      }      ListNode nodeFirst = node;      ListNode nodeLast = node;        while (count != 0) {          count--;          nodeFirst = nodeFirst.next;      }     while (nodeFirst != nodeLast) {          nodeFirst = nodeFirst.next;          nodeLast = nodeLast.next;     }     return nodeFirst;  }

总结：其实就是三步曲：先找到在环中相遇的节点、再求出环的大小、最后得到环开始的节点。