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

總結：其實就是三步曲：先找到在環中相遇的節點、再求出環的大小、最後得到環開始的節點。

Tags:

VirMach 便宜 VPS