題目描述：

給一個長度為n鏈表，若其中包含環，請找出該鏈表的環的入口結點，否則，返回null。

數據范圍： n≤10000，1<=結點值<=10000

要求：空間復雜度 O(1)，時間復雜度 O(n)

例如，輸入{1,2},{3,4,5}時，對應的環形鏈表如下圖所示：

可以看到環的入口結點的結點值為3，所以返回結點值為3的結點。

輸入描述：

輸入分為2段，第一段是入環前的鏈表部分，第二段是鏈表環的部分，后臺會根據第二段是否為空將這兩段組裝成一個無環或者有環單鏈表

返回值描述：

返回鏈表的環的入口結點即可，我們后臺程序會打印這個結點對應的結點值；若沒有，則返回對應編程語言的空結點即可。

示例：

輸入：

{1,2},{3,4,5}

返回值：

3

說明：

返回環形鏈表入口結點，我們后臺程序會打印該環形鏈表入口結點對應的結點值，即3

解題思路：

本題考察數據結構鏈表的使用，有兩種解法。

1. 哈希Set。用容器哈希Set遍歷存儲指針，當某次存儲發現容器中已有該指針，說明此時已經到了環形鏈表入口。
2. 快慢雙指針法。如下圖所示，快指針以慢指針兩倍的速度前進，當他們第一次相遇時，慢指針走了X+Y，快指針走了2*(X+Y)，其中AB為X，BC為Y，那CB順指針的距離就是2*(X+Y)-X-2*Y=X，此時將快指針放到頭節點A處，讓它們以相同速度前進，到B時正好相遇，也就是入口結點。

測試代碼：

解法一：哈希Set

/*
struct ListNode {
  int val;
  struct ListNode *next;
  ListNode(int x) :
      val(x), next(NULL) {
  }
};
*/
class Solution {
public:
  ListNode* EntryNodeOfLoop(ListNode* pHead) {
      unordered_set<ListNode*> S;
      while(pHead)
      {
          if(S.find(pHead)= = S.end())
          {
              S.insert(pHead);
              pHead = pHead->next;
          }
          else{
              return pHead;
          }
      }
      return nullptr;
  }
};

解法二：快慢雙指針 

/*
struct ListNode {
  int val;
  struct ListNode *next;
  ListNode(int x) :
      val(x), next(NULL) {
  }
};
*/
class Solution {
public:
  ListNode* EntryNodeOfLoop(ListNode* pHead) {
      // 空指針返回
      if(pHead == nullptr) 
          return nullptr;
      
      // 定義雙指針
      ListNode* slow = pHead;
      ListNode* fast = pHead;
      
      // 當能形成閉路時，while才會無限循環直到break
      while(fast != nullptr && fast->next != nullptr)
      {
          // 快指針以兩倍速度前進
          fast = fast->next->next;
          slow = slow->next;
          if(slow == fast)
              break;
      }
      
      // 若指向空指針，說明沒有形成閉路
      if(fast == nullptr || fast->next == nullptr)
          return nullptr;
      
      // 將快指針指向頭
      fast = pHead;
      
      // 當他倆相遇時，就是環形鏈表入口處
      while(fast != slow)
      {
          fast = fast->next;
          slow = slow->next;
      }
      
      return fast;
  }
};

到此這篇關于如何通過C++求出鏈表中環的入口結點的文章就介紹到這了,更多相關C++ 鏈表中環的入口結點內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！

原文鏈接：https://blog.csdn.net/zhaitianbao/article/details/121848094