題目描述：

給一個(gè)長(zhǎng)度為n鏈表，若其中包含環(huán)，請(qǐng)找出該鏈表的環(huán)的入口結(jié)點(diǎn)，否則，返回null。

數(shù)據(jù)范圍： n≤10000，1<=結(jié)點(diǎn)值<=10000

要求：空間復(fù)雜度 O(1)，時(shí)間復(fù)雜度 O(n)

例如，輸入{1,2},{3,4,5}時(shí)，對(duì)應(yīng)的環(huán)形鏈表如下圖所示：

可以看到環(huán)的入口結(jié)點(diǎn)的結(jié)點(diǎn)值為3，所以返回結(jié)點(diǎn)值為3的結(jié)點(diǎn)。

輸入描述：

輸入分為2段，第一段是入環(huán)前的鏈表部分，第二段是鏈表環(huán)的部分，后臺(tái)會(huì)根據(jù)第二段是否為空將這兩段組裝成一個(gè)無環(huán)或者有環(huán)單鏈表

返回值描述：

返回鏈表的環(huán)的入口結(jié)點(diǎn)即可，我們后臺(tái)程序會(huì)打印這個(gè)結(jié)點(diǎn)對(duì)應(yīng)的結(jié)點(diǎn)值；若沒有，則返回對(duì)應(yīng)編程語言的空結(jié)點(diǎn)即可。

示例：

輸入：

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

返回值：

3

說明：

返回環(huán)形鏈表入口結(jié)點(diǎn)，我們后臺(tái)程序會(huì)打印該環(huán)形鏈表入口結(jié)點(diǎn)對(duì)應(yīng)的結(jié)點(diǎn)值，即3

解題思路：

本題考察數(shù)據(jù)結(jié)構(gòu)鏈表的使用，有兩種解法。

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

測(cè)試代碼：

解法一：哈希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;
      
      // 當(dāng)能形成閉路時(shí)，while才會(huì)無限循環(huán)直到break
      while(fast != nullptr && fast->next != nullptr)
      {
          // 快指針以兩倍速度前進(jìn)
          fast = fast->next->next;
          slow = slow->next;
          if(slow == fast)
              break;
      }
      
      // 若指向空指針，說明沒有形成閉路
      if(fast == nullptr || fast->next == nullptr)
          return nullptr;
      
      // 將快指針指向頭
      fast = pHead;
      
      // 當(dāng)他倆相遇時(shí)，就是環(huán)形鏈表入口處
      while(fast != slow)
      {
          fast = fast->next;
          slow = slow->next;
      }
      
      return fast;
  }
};

到此這篇關(guān)于如何通過C++求出鏈表中環(huán)的入口結(jié)點(diǎn)的文章就介紹到這了,更多相關(guān)C++ 鏈表中環(huán)的入口結(jié)點(diǎn)內(nèi)容請(qǐng)搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！

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