1環(huán)形鏈表 II

給定一個鏈表的頭節(jié)點(diǎn) ?head?，返回鏈表開始入環(huán)的第一個節(jié)點(diǎn)。?如果鏈表無環(huán)，則返回?null。

如果鏈表中有某個節(jié)點(diǎn)，可以通過連續(xù)跟蹤?next?指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評測系統(tǒng)內(nèi)部使用整數(shù)?pos?來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果?pos?是?-1，則在該鏈表中沒有環(huán)。注意：pos?不作為參數(shù)進(jìn)行傳遞，僅僅是為了標(biāo)識鏈表的實(shí)際情況。

不允許修改?鏈表。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節(jié)點(diǎn)
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點(diǎn)。

示例?2：

輸入：head = [1,2], pos = 0
輸出：返回索引為 0 的鏈表節(jié)點(diǎn)
解釋：鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點(diǎn)。

示例 3：

輸入：head = [1], pos = -1
輸出：返回 null
解釋：鏈表中沒有環(huán)。

提示：

• 鏈表中節(jié)點(diǎn)的數(shù)目范圍在范圍?[0, 104]?內(nèi)
• -105 <= Node.val <= 105
• pos?的值為?-1?或者鏈表中的一個有效索引

思路：

1. 初始化指針：

   • 使用兩個指針?fast?和?slow，初始時都指向鏈表的頭節(jié)點(diǎn)?head。

2. 檢測環(huán)：

   • 在一個?while?循環(huán)中，不斷移動?fast?和?slow?指針，直到?fast?或?fast->next?變?yōu)?NULL?或者?fast?和?slow?指針相遇。
   • fast?指針每次移動兩步（fast = fast->next->next）。
   • slow?指針每次移動一步（slow = slow->next）。
   • 當(dāng)?fast?和?slow?指針相遇時，說明鏈表中存在環(huán)。

3. 檢查是否有環(huán)：

   • 如果?fast?或?fast->next?變?yōu)?NULL，說明鏈表沒有環(huán)，此時返回?NULL。

4. 找到環(huán)的入口：

   • 當(dāng)快慢指針相遇后，將?fast?指針重新指向鏈表的頭節(jié)點(diǎn)?head。
   • 然后讓?fast?和?slow?指針同時每次移動一步，直到它們再次相遇。
   • 二者相遇的節(jié)點(diǎn)就是環(huán)的入口節(jié)點(diǎn)。

5. 返回環(huán)的入口節(jié)點(diǎn)：

   • 返回?fast?或?slow?指針，它們此時指向環(huán)的入口節(jié)點(diǎn)。

代碼：

struct ListNode *detectCycle(struct ListNode *head) {// 使用快慢指針檢測是否有環(huán)struct ListNode* fast = head;struct ListNode* slow = head;while (true) {// 如果快指針或快指針的下一個節(jié)點(diǎn)為 nullptr，直接返回 nullptrif (fast == nullptr || fast->next == nullptr) {return nullptr; }fast = fast->next->next; // 快指針移動兩步slow = slow->next;       // 慢指針移動一步// 檢查快慢指針是否相遇if (fast == slow) {break; // 找到環(huán)}}// 找到環(huán)的入口fast = head; // 將快指針重置到頭節(jié)點(diǎn)while (fast != slow) {fast = fast->next; // 快指針和慢指針同時移動一步slow = slow->next;}// 返回環(huán)的入口節(jié)點(diǎn)return fast;
}

2有效的括號

給定一個只包括?'('，')'，'{'，'}'，'['，']'?的字符串?s?，判斷字符串是否有效。

有效字符串需滿足：

1. 左括號必須用相同類型的右括號閉合。
2. 左括號必須以正確的順序閉合。
3. 每個右括號都有一個對應(yīng)的相同類型的左括號。

示例 1：

輸入：s = "()"

輸出：true

示例 2：

輸入：s = "()[]{}"

輸出：true

示例 3：

輸入：s = "(]"

輸出：false

示例 4：

輸入：s = "([])"

輸出：true

提示：

• 1 <= s.length <= 104
• s?僅由括號?'()[]{}'?組成

思路：

先來分析一下 這里有三種不匹配的情況，

第一種情況，字符串里左方向的括號多余了 ，所以不匹配。（第一種情況：已經(jīng)遍歷完了字符串，但是棧不為空，說明有相應(yīng)的左括號沒有右括號來匹配，所以return false） 第二種情況，括號沒有多余，但是 括號的類型沒有匹配上。（第二種情況：遍歷字符串匹配的過程中，發(fā)現(xiàn)棧里沒有要匹配的字符。所以return false）

第三種情況，字符串里右方向的括號多余了，所以不匹配。（遍歷字符串匹配的過程中，棧已經(jīng)為空了，沒有匹配的字符了，說明右括號沒有找到對應(yīng)的左括號return false） 我們的代碼只要包含這三種不匹配的情況，就不會出問題

字符串遍歷完之后，棧是空的，就說明全都匹配了。

代碼：

bool isValid(char * s) {int len = strlen(s);// 為棧分配內(nèi)存，棧最多能存儲 len 個元素char* stack = malloc(sizeof(char) * len); int count = 0; // 棧的當(dāng)前大小// 遍歷字符串中的每個字符for (int i = 0; i < len; i++) {// 如果是左括號，壓入棧中if (s[i] == '(' || s[i] == '{' || s[i] == '[') {stack[count++] = s[i]; // 將左括號壓入棧中} // 如果是右括號，進(jìn)行匹配檢查else {// 檢查當(dāng)前棧是否為空，或棧頂?shù)淖罄ㄌ柺欠衽c當(dāng)前右括號匹配if (count == 0) {// 情況 3：遍歷字符串匹配的過程中，棧已經(jīng)為空了，沒有匹配的字符了，說明右括號沒有找到對應(yīng)的左括號return false; }char top = stack[count - 1]; // 獲取棧頂元素// 檢查匹配if ((s[i] == ')' && top == '(') || (s[i] == '}' && top == '{') || (s[i] == ']' && top == '[')) {count--; // 匹配成功，彈出棧頂元素} else {// 情況 2：遍歷字符串匹配的過程中，發(fā)現(xiàn)棧里沒有要匹配的字符return false; }}}// 情況 1：已經(jīng)遍歷完了字符串，但是棧不為空，說明有相應(yīng)的左括號沒有右括號來匹配return count == 0; // 返回 true，表示有效；否則返回 false，無效
}