一、环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
方法（快慢指针）：
我们定义两个指针，一快一慢。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针和快指针都在位置 head出发。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool hasCycle(struct ListNode *head) { struct ListNode* slow = head,*fast = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) { return true; } } return false; }
时间复杂度：O(N)O(N)O(N)，其中 NNN 是链表中的节点数。
当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。
当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 NNN 轮。
空间复杂度：O(1)O(1)O(1)。我们只使用了两个指针的额外空间。
二、环形链表 II
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
快慢指针：
此题解题思路同上一题
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* slow = head,*fast = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; //推到的一个结论:一个指针从相遇点开始走,一个指针从head走,他们会在入口点相遇 if(slow == fast) { struct ListNode* meet = slow; while(head != meet) { head = head->next; meet = meat->next; } return meet; } } return NULL; }
三、有效的括号
此题C语言不方便解释，只讲解思路
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
1、左括号必须用相同类型的右括号闭合。
2、左括号必须以正确的顺序闭合。
3、每个右括号都有一个对应的相同类型的左括号。
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
typedef char STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST; void StackInit(ST* ps) { ps->a = (STDataType*)malloc(sizeof(STDataType) * 4); if (ps->a == NULL) { printf("malloc fail\n"); exit(-1); } ps->capacity = 4; ps->top = 0; } void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } //入栈 void StackPush(ST* ps, STDataType x) { assert(ps); //满了 -> 增容 if (ps->top == ps->capacity) { STDataType* tmp = realloc(ps->a, ps->capacity * 2 * sizeof(int)); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } else { ps->a = tmp; ps->capacity *= 2; } } ps->a[ps->top] = x; ps ->top++; } //出栈 void StackPop(ST* ps) { assert(ps); //ps->a[ps->top - 1] = 0; //此处有两种情况: //一、ps->a[ps->top - 1]本身就是0 //二、ps->a[ps->top - 1]的数据类型不是int，是其他数据类型 assert(ps->top > 0); //栈空了，调用Pop，直接中止程序报错 ps->top--; } STDataType StackTop(ST* ps) { assert(ps); //栈空了,调用Top,直接中止程序报错 assert(ps->top > 0); return ps->a[ps->top - 1]; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; }
函数内部使用了一个名为ST的栈数据结构，并通过调用StackInit函数进行初始化。栈用于存储左括号（{、[、(），以便后续与右括号进行匹配。
代码的主要逻辑是一个while循环，遍历输入字符串s中的每个字符，直到遇到字符串的结束符\0。在循环中，根据当前字符的不同情况进行处理：
- 如果当前字符是左括号（
{、[、(），则将其推入栈中，并移动指针s指向下一个字符。 - 如果当前字符是右括号（
}、]、)），则进行以下操作：
- 首先检查栈是否为空，如果为空，则说明没有匹配的左括号，直接返回
false表示字符串无效。 - 如果栈不为空，则取出栈顶元素（即最近推入的左括号），并与当前右括号进行匹配。
- 如果匹配成功（即左括号和右括号匹配），则将栈顶元素弹出，并移动指针
s指向下一个字符。 - 如果匹配失败，则直接返回
false表示字符串无效。
- 如果当前字符不是括号，则直接跳过该字符。
循环结束后，检查栈是否为空。如果栈为空，则说明所有左括号都与右括号成功匹配，返回true表示字符串有效；否则返回false表示字符串无效。
最后，在返回结果之前，调用StackDestroy函数销毁栈，释放相关资源。
bool isValid(char* s) { ST st; StackInit(&st); while (*s != '\0') { switch (*s) { case'{': case'[': case'(': { StackPush(&st, *s); ++s; break; } case'}': case']': case')': { if (StackEmpty(&st)) { StackDestroy(&st); return false; } char top = StackTop(&st); StackPop(&st); //不匹配 if ((*s == '}' && top != '{') || (*s == ']' && top != '[') || (*s == ')' && top != '(')) { return false; } else //匹配 { ++s; } break; } default: break; } } bool ret = StackEmpty(&st); StackDestroy(&st); return ret; }
今天就先到这了！！！
看到这里了还不给博主扣个：
⛳️ 点赞☀️收藏 ⭐️ 关注！
你们的点赞就是博主更新最大的动力！
有问题可以评论或者私信呢秒回哦。
