一.链表内指定区间反转：链表内指定区间反转_牛客题霸_牛客网 (nowcoder.com)
描述
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n),空间复杂度O(1)
例如：给出的链表为1→2→3→4→5→NULL m=2,n=4,
返回 1→4→3→2→5→NULL
解题思路
如果只有一个节点或者m==n，那就直接返回head，因为不用反转。如果有多个节点，那就需要建立一个哨兵位标记住头节点，后续需要移动头节点。然后找到反转位置的前驱节点，再将反转位置赋值给head，将m到n之间的节点取下来头插就可以达到反转链表的效果。（head会随着不断头插向后挪动，需要用一个next指针记住head的下一个节点），此外要注意好区间范围的控制。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZB1Dlp1l-1679744040656)(C:\Users\羽北冥\AppData\Roaming\Typora\typora-user-images\image-20230325131417710.png)]
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) { // write code here //如果只有一个节点或者没有节点就直接返回 if(head==NULL||head->next==NULL||m==n) return head; //如果有多个节点，就建立一个哨兵位节点,找到反转位置拿下来头插 struct ListNode*tmp=(struct ListNode*)malloc(sizeof(struct ListNode)); tmp->next=head; struct ListNode*prev=tmp; for(int i=1;i<m;i++) { prev=prev->next; } //将需要反转链表的头部搞给head head=prev->next; for(int j=m;j<n;j++) { //将节点取下来头插 struct ListNode*next=head->next; head->next=next->next; next->next=prev->next; prev->next=next; } head=tmp->next; free(tmp); return head; }
二.从链表中删去总和值为零的连续节点：1171. 从链表中删去总和值为零的连续节点 - 力扣（LeetCode）
描述
给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。
删除完毕后，请你返回最终结果链表的头节点。
你可以返回任何满足题目要求的答案（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）
示例 1：
输入：head = [1,2,-3,3,1] 输出：[3,1] 提示：答案 [1,2,1] 也是正确的。
解题思路
首先要明确一点：这个数组不是绝对有序的（因为我当时考虑了哈哈）。
核心就是只要前面的数值相加结果等于零，那么前面所有的节点都可以舍弃。但是你直接从零位置开始累加的话不一定会得到前缀和能为零，所以这里可以考虑使用嵌套循环，也就是说如果从第一个位置累加不能为零，那么就从第二个位置再累加一次。直接走完所有的节点都不能累加为零，就说明所有的数都是正数。
struct ListNode* removeZeroSumSublists(struct ListNode* head){ struct ListNode*phead=(struct ListNode*)malloc(sizeof(struct ListNode)); phead->next=head; //用双指针嵌套循环 struct ListNode*cur=phead; struct ListNode*curr=cur->next; int sum=0; while(cur) { sum=0;//这里必须在更新一下保证第二次循环不被影响 curr=cur->next;//这里怎么能不更新curr while(curr) { sum+=curr->val; if(sum==0) { cur->next=curr->next;//不释放节点，直接更新cur位置 } curr=curr->next; } cur=cur->next; } return phead->next; }
三.链表求和：面试题 02.05. 链表求和 - 力扣（LeetCode）
描述
给定两个用链表表示的整数，每个节点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。
示例：
输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295 输出：2 -> 1 -> 9，即912
解题思路
我最开始想着设定两个变量然后分别循环遍历两个链表，将两个链表中得到的值存储给变量n1，n2，最后两者相加得到sum，再对sum做文章。但是这样要走两次循环，后面我有思考了一下发现可以直接相加。
除n1和n2以外，在设定一个carry变量用来保存进位（对于加法来说如果这两个数相加大于十，则要往前进一位，再将这一位加给十位相加得到的结果），可以直接将这三个变量相加的结果存放到链表中。需要注意的是链表最后的节点相加可能超过十，所以出了循环以后要对carry判断一下，如果carry不为零，则还要开一个节点存放carry
此外设置一个head和一个tail指针，在第一次插入的时候初始化head，后续只动tail指针，最后用head做返回值。
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { int n1,n2=0; int carry=0,sum=0; struct ListNode*head=NULL,*tail=NULL; while(l1||l2)//如果两个都是空就没有意义了 { n1=l1?l1->val:0;//如果l1不是空，就返回它的值否则返回0 n2=l2?l2->val:0; sum=n1+n2+carry; if(head==NULL) { head=tail=(struct ListNode*)malloc(sizeof(struct ListNode)); tail->val=sum%10;//sum的值可能超过十，我们只需要存sum的个位就行 tail->next=NULL; } else { //不是第一次插入,只动尾节点 tail->next=(struct ListNode*)malloc(sizeof(struct ListNode)); tail->next->val=sum%10; tail=tail->next; tail->next=NULL; } carry=sum/10;//更新carry //如果了l1和l2不为空就继续往下走 if(l1) l1=l1->next; if(l2) l2=l2->next; } if(carry>0) { tail->next=(struct ListNode*)malloc(sizeof(struct ListNode)); tail->next->val=carry; tail->next->next=NULL; } return head; }
四.括号的最大嵌套深度：1614. 括号的最大嵌套深度 - 力扣（LeetCode）
描述
如果字符串满足以下条件之一，则可以称之为 有效括号字符串（valid parentheses string，可以简写为 VPS）：
字符串是一个空字符串 “”，或者是一个不为 “(” 或 “)” 的单字符。
字符串可以写为 AB（A 与 B 字符串连接），其中 A 和 B 都是 有效括号字符串 。
字符串可以写为 (A)，其中 A 是一个 有效括号字符串 。
类似地，可以定义任何有效括号字符串 S 的 嵌套深度 depth(S)：
depth(“”) = 0
depth© = 0，其中 C 是单个字符的字符串，且该字符不是 “(” 或者 “)”
depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是 有效括号字符串
depth(“(” + A + “)”) = 1 + depth(A)，其中 A 是一个 有效括号字符串
例如：“”、“()()”、“()(()())” 都是 有效括号字符串（嵌套深度分别为 0、1、2），而 “)(” 、“(()” 都不是 有效括号字符串 。
给你一个 有效括号字符串 s，返回该字符串的 s 嵌套深度 。
示例 1：
输入：s = "(1+(2*3)+((8)/4))+1" 输出：3 解释：数字 8 在嵌套的 3 层括号中。
解题思路
这类题目用栈会比较好处理，但是C语言如果要使用栈的话，又要徒手写一个，这样太耗费时间了。所以这里可以采用一个数组通过下标的控制来达到模拟栈的效果。
如果是左括号就将其入栈，如果是右括号就将左括号出栈。也就是说如果是 “（ ”则size–，如果是 “ ）”则size++，以此来表示栈内容量的变化。在不断入栈出栈的过程中，size的最大值就是括号的最大嵌套深度，因为s是一个有效的括号字符串。
#define MAX(a,b) ((a)>(b)?(a):(b)) int maxDepth(char * s) { int len=strlen(s); int size=0; for(int i=0;i<len;i++) { if(s[i]=="(") size++; ans=MAX(size,ans); if(s[i]==")") size--; } return ans; }
其实就是拥有左括号数的最大值
最近铃芽之旅上线了不知道各位有没有去看（又有多少老铁是一个人去看的，斜眼笑），昨天我可是特意给你们放了假（好吧，其实是昨天课太多了，而我又被某些题目卡了三个小时所以才没来得及，菜鸡流泪）。
人们总是高估短期努力能够带来的提升，却忽略长期坚持能带来的改变。今天是第六天了，你还有坚持吗？
