数据结构练习题5（链表和栈）

1环形链表 II

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

• 链表中节点的数目范围在范围 [0, 104] 内
• -105 <= Node.val <= 105
• pos 的值为 -1 或者链表中的一个有效索引

思路：

1. 初始化指针：

   • 使用两个指针 fast 和 slow，初始时都指向链表的头节点 head。

2. 检测环：

   • 在一个 while 循环中，不断移动 fast 和 slow 指针，直到 fast 或 fast->next 变为 NULL 或者 fast 和 slow 指针相遇。
   • fast 指针每次移动两步（fast = fast->next->next）。
   • slow 指针每次移动一步（slow = slow->next）。
   • 当 fast 和 slow 指针相遇时，说明链表中存在环。

3. 检查是否有环：

   • 如果 fast 或 fast->next 变为 NULL，说明链表没有环，此时返回 NULL。

4. 找到环的入口：

   • 当快慢指针相遇后，将 fast 指针重新指向链表的头节点 head。
   • 然后让 fast 和 slow 指针同时每次移动一步，直到它们再次相遇。
   • 二者相遇的节点就是环的入口节点。

5. 返回环的入口节点：

   • 返回 fast 或 slow 指针，它们此时指向环的入口节点。

代码：

struct ListNode *detectCycle(struct ListNode *head) {// 使用快慢指针检测是否有环struct ListNode* fast = head;struct ListNode* slow = head;while (true) {// 如果快指针或快指针的下一个节点为 nullptr，直接返回 nullptrif (fast == nullptr || fast->next == nullptr) {return nullptr; }fast = fast->next->next; // 快指针移动两步slow = slow->next;       // 慢指针移动一步// 检查快慢指针是否相遇if (fast == slow) {break; // 找到环}}// 找到环的入口fast = head; // 将快指针重置到头节点while (fast != slow) {fast = fast->next; // 快指针和慢指针同时移动一步slow = slow->next;}// 返回环的入口节点return fast;
}

2有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"

输出：true

示例 2：

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

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([])"

输出：true

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

思路：

先来分析一下 这里有三种不匹配的情况，

第一种情况，字符串里左方向的括号多余了 ，所以不匹配。（第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false） 第二种情况，括号没有多余，但是 括号的类型没有匹配上。（第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false）

第三种情况，字符串里右方向的括号多余了，所以不匹配。（遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false） 我们的代码只要包含这三种不匹配的情况，就不会出问题

字符串遍历完之后，栈是空的，就说明全都匹配了。

代码：

bool isValid(char * s) {int len = strlen(s);// 为栈分配内存，栈最多能存储 len 个元素char* stack = malloc(sizeof(char) * len); int count = 0; // 栈的当前大小// 遍历字符串中的每个字符for (int i = 0; i < len; i++) {// 如果是左括号，压入栈中if (s[i] == '(' || s[i] == '{' || s[i] == '[') {stack[count++] = s[i]; // 将左括号压入栈中} // 如果是右括号，进行匹配检查else {// 检查当前栈是否为空，或栈顶的左括号是否与当前右括号匹配if (count == 0) {// 情况 3：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false; }char top = stack[count - 1]; // 获取栈顶元素// 检查匹配if ((s[i] == ')' && top == '(') || (s[i] == '}' && top == '{') || (s[i] == ']' && top == '[')) {count--; // 匹配成功，弹出栈顶元素} else {// 情况 2：遍历字符串匹配的过程中，发现栈里没有要匹配的字符return false; }}}// 情况 1：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配return count == 0; // 返回 true，表示有效；否则返回 false，无效
}