每日鸡汤：
? ? ? ? ? ? ? ? 🚀有点累了
目录
一、删除链表的倒数第N个结点
给你一个链表，删除链表的倒数第?
n?个结点，并且返回链表的头结点。
①快慢指针
常规的方法，遍历数数，计算有多少个结点，得出倒数第n个节点是正数第几个节点，删除然后返回。这种方式比较挫，也不推荐。博主比较推荐的这道题目的解题方式是使用快慢指针的方式。具体来说就是指定一个fast指针，让它先走n步，然后让slow指针和fast指针同步开始走，当fast指针指向空的时候，slow指针就是我们要删除的节点。这种设计的理念在于：
1、倒数第n个节点是相比于最后一个节点的next相差n步，所以我们才让fast和slow相差n步，当fast到NULL，slow恰好就是倒数第n个节点。
2、这道题目还需要注意当我们要删除倒数第n个节点的时候，要把要删除的节点的前一个节点和它的后一个节点链接起来。
3、注意如果要删除的是头节点，需要额外考虑，这里建议的解决方案是增加一个哨兵节点。
struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
if(head==NULL||(head->next==NULL&&n==1))
return NULL;
struct ListNode* guard=(struct ListNode*)malloc(sizeof(struct ListNode));
if(guard==NULL)
{
perror("malloc fail");
exit(-1);
}
guard->next=head;
struct ListNode* fast=head;
struct ListNode* slow=head;
struct ListNode* prev=head;
while(n--)
{
fast=fast->next;
}
while(fast)
{
prev=slow;
slow=slow->next;
fast=fast->next;
}
if(slow==head)
{
guard->next=slow->next;//考虑到头的问题
}
else
{
prev->next=slow->next;
}
head=guard->next;
free(slow);
free(guard);
return head;
}二、环形链表的约瑟夫问题
链接：环形链表的约瑟夫问题__牛客网
来源：牛客网
据说著名犹太历史学家 Josephus?有过以下故事：在罗马人占领乔塔帕特后，39 个犹太人与 Josephus?及他的朋友躲到一个洞中，39?个犹太人决定宁愿死也不要被敌人抓到，于是决定了一种自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，报数到 3?的人就自杀，然后再由下一个人重新报 1，报数到 3?的人再自杀，这样依次下去，直到剩下最后一个人时，那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链表得出最终存活的人的编号。
输入描述:
一行两个整数 n 和 m， n 表示环形链表的长度， m 表示每次报数到 m 就自杀。
输出描述:
输出最后存活下来的人编号(编号从1开始到n)
①暴力求解
这道题目环形链表的问题，当数到m的时候，就销毁这个节点然后把这个节点的前后节点链接起来，当只剩下一个节点的时候，就可以打印这个节点的值。这是比较普适的解法。比较麻烦的是，我们得自己写一个环形链表，让他们链接起来，其余逻辑比较简单。
#include<iostream>
using namespace std;
typedef struct ListNode
{
struct ListNode* next;
int val;
}ListNode;
ListNode* NewList(int i)
{
ListNode* NewNode=(ListNode*)malloc(sizeof(ListNode));
if(NewNode==nullptr)
{
perror("malloc fail");
exit(-1);
}
NewNode->next=nullptr;
NewNode->val=i;
return NewNode;
}
ListNode* CreateList(int n)
{
int i=1;
ListNode* head=NewList(i);
++i;
ListNode* cur=head;
while(i<=n)
{
ListNode* newnode=NewList(i);
cur->next=newnode;
cur=cur->next;
cur->next=head;
++i;
}
return head;
}
int main()
{
//先写一个链表
//创建链表
int n,m;
cin>>n>>m;
if(n<2)
cout<<n;
ListNode*cur=CreateList(n);
ListNode* prev=nullptr;
ListNode* next=cur->next;
int count=1;
while(next!=cur)
{
if(count!=m)
{
prev=cur;
cur=next;
next=next->next;
count++;
}
else
{
prev->next=next;
free(cur);
cur=next;
next=next->next;
count=1;
}
}
cout<<cur->val;
free(cur);
return 0;
}当然还有一种数学关系的解法，不过博主没咋懂代码的意思，也能跑过去，看起来非常简便，连链表都不用写。
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m, s=0;
scanf("%d%d", &n, &m);
for(int i=2;i<=n;i++)
s = (s+m)%i;
printf("%d\n", s+1);
return 0;
}三、两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
①迭代
①、迭代
两两交换，暴力遍历交换思想比较简单，但是需要注意颇多的细节，
1、对于前两个节点比较简单，先把第三个节点存下来，然后把第二个节点的next指向第一个节点，第一个节点的next指向第三个节点，这时候头就发生了变化；
2、前两个节点的交换考虑的比较少，比较容易出错的地方是对于后序节点的考虑，对于第二组两两交换的节点，需要注意的是你不只是交换这两个节点，你还需要考虑
?你还要考虑1的next变成了4，而不是3，所以这要求你得再添加一个节点去保存上一个节点。
3、特殊情况就是为空，或者只有一个节点无法完成两两交换。
struct ListNode* swapPairs(struct ListNode* head)
{
if(head==NULL||head->next==NULL)
{
return head;
}
struct ListNode* prev=NULL;
struct ListNode* tail=head;
struct ListNode* cur=tail->next;
head=head->next;
while(tail&&cur)
{
struct ListNode* next=cur->next;
cur->next=tail;
tail->next=next;
if(prev)
{
prev->next=cur;
}
prev=tail;
tail=next;
if(tail)
cur=tail->next;
}
return head;
}②递归?
这道题目可以采用递归的理由是，它有大量重复的操作，以及合适的终止条件--只有一个节点或者为空。
递归的思考要求我们缩小到一个小的区间去考虑问题：
?我们划定前两个来考虑递归的普适性问题：
1、节点间的关系考虑，1和2的关系先改变还是先改变1的next指向2的next呢？显然是先改变1的next，因为我们先改变1和2的关系，就会导致找不到节点3.所以递归逻辑很简单
2、结束条件：当head为空或者只有一个head就为空。
struct ListNode* swapPairs(struct ListNode* head)
{
if (head == NULL || head->next == NULL)
{
return head;
}
struct ListNode* newHead = head->next;
head->next = swapPairs(newHead->next);
newHead->next = head;
return newHead;
}四、K个一组翻转链表
给你链表的头节点 head ，每?k?个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是?k?的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
①迭代求解
这道题目并不复杂，和上道题目大同小异，也是有迭代和递归解法。
①迭代
1、这道题有道坑，逆序k个节点，实际我们进行了k-1次操作，如果中间的迭代进行重复操作，当第k-1次操作的时候，我们需要单独拎出来进行处理前后衔接和头节点发生变换的问题。
2、我们需要遍历知道有多少个节点，每进行一组逆序之后，我们总的节点都要减去一组，剩余的节点如果不够一组就没必要翻转了。
3、迭代思想很简单，但是代码细节需要注意的颇多，你需要单独考虑第一组头节点发生变化的情况，和记录上一组的尾，因为下一组发生逆转之后，上一组的尾的next就要发生变化！！
4、不需要逆序就是节点数小于一组需要翻转的数目或者一组需要翻转的数目为1.
struct ListNode* reverseKGroup(struct ListNode* head, int k)
{
struct ListNode * tail = head;
struct ListNode * n2 = head;
struct ListNode * newhead = head;
struct ListNode * n3 = n2->next;
int length = 0;
int flag = 1;
while (tail)
{
tail = tail->next;
length++;
}
if (length < k||k==1)
{
return head;
}
while (length >= k)
{
int m = k;
while (--m)
{
//对于m==0需要特别处理
struct ListNode * next = n3->next;
if (m == 1)
{
n3->next = n2;
n2 = n3;
newhead->next = next;
if (tail)
{
tail->next = n2;
tail = newhead;
}
else
{
tail = newhead;
}
newhead = next;
if (flag == 1)
{
head = n2;
flag--;
}
//上一个尾
n2 = next;
if(n2)
n3 = n2->next;
}
else
{
n3->next = n2;
n2 = n3;
n3 = next;
}
}
length -= k;
}
return head;
}②递归求解?
②递归
1、递归挺简单的，和上一组逆序一样，我们中间的过程不需要太多注意，就是对于每组最后一次操作的时候，我们要注意
?先动head和newhead->next的关系还是newhead和tail的关系？
2、结束条件就是剩余节点数小于要求翻转数或者翻转数为1.
3、递归唯一的缺点就是对栈的消耗比较大。
struct ListNode* Reverse(struct ListNode*head,int k,int restlength)
{
if(restlength<k||k==1)
{
return head;
}//结束条件是剩余的没有k个了不需要反转
struct ListNode* tail=head;
struct ListNode* newhead=NULL;
struct ListNode* next=tail->next;
int m=k-1;//进行了k-1次
while(m>1)
{
newhead=next;
next=newhead->next;
newhead->next=tail;
tail=newhead;
m--;
}
//需要处理
newhead=next;
head->next=Reverse(newhead->next,k,restlength-k);
newhead->next=tail;
return newhead;
}
struct ListNode* reverseKGroup(struct ListNode* head, int k)
{
int length=0;
struct ListNode* cur=head;
while(cur)
{
length++;
cur=cur->next;
}
//计算全部长度
head= Reverse(head,k,length);
return head;
}五、最长有效括号
给你一个只包含?
'('?和?')'?的字符串，找出最长有效（格式正确且连续）括号子串的长度。
这道题目平常的思路真的不好想。我们还是先看一下几个测试用例：
?emm，比较恶心，刚开始没想到的情况是第二种，然后被第三种和第四种恶心到了。
但是我们注意到一个特点：就是碰到右括号代表如果栈中没有和它匹配的左括号，就代表计算一段有效长度括号的结束，我们需要重新开始！！
这道题目主流的解法有三种：1、动态规划(没学，不会)；2、栈；3、正向逆向结合法。
①栈（非常规）
虽说是用栈的方法，不如说是借用了栈的思想，通过下标的方式计算长度。
?这里初始化栈的第一个元素为-1有妙用，我们这是在模拟第一个元素为’）‘，但它不是真的’）‘。
它的用处是：
如果碰到元素就是‘）’，而此时栈里面只有-1，那么我们就把元素-1弹出去，把栈顶更新为‘）’的下标，因为每当计算最长有效括号终止的原因就是碰到右括号，但同时他也是新的计算长度的开始，但是刚开始没有‘）’，所以我们要模拟一个出来！！
如果碰到左括号，就入栈它的下标，如果遇到右括号就拿出来匹对。计算下标差异得出最长长度。
int longestValidParentheses(char * s)
{
int length=strlen(s);
int stk[length+1];
int top=-1;
stk[++top]=-1;
int maxlength=0;
for(int i=0;i<length;++i)
{
if(s[i]=='(')
{
stk[++top]=i;
}
else
{
//不是左括号
top--;
if(top==-1)
{
stk[++top]=i;//标记右括号
}
else
{
maxlength=fmax(maxlength,i-stk[top]);
}
}
}
return maxlength;
}②正逆结合的方式
这种方式十分巧妙，通过一次正向遍历和一次逆向遍历就可以得出最长长度！
1、如果左括号和右括号的个数相等，就更新最长有效括号为它们的和或任意一个个数的两倍。
2、正向遍历：如果右括号的个数多于左括号，那么就不可能再有左括号和它匹配，就结束这一次计数。
3、逆向遍历：如果左括号的个数多于右括号，那么就不可能再有右括号和它匹配，就结束这一次计数。
说明：
为什么不进行一次遍历？因为只有正向会有左括号个数多于右括号而没有更新最长有效括号的情况：
?没有更新最长，而当正向左括号多于右括号的情况时，反向肯定可以求出最长有括号，互补，所以两次遍历就可以求出！！
int longestValidParentheses(char * s)
{
int left=0;
int right=0;
int maxans=0;
int n=strlen(s);
//正是找右括号
for(int i=0;i<n;++i)
{
if(s[i]=='(')
{
left++;
}
else
{
right++;
}
if(left==right)
{
maxans=fmax(maxans,2*right);
}
else if(right>left)
{
left=right=0;
}
}
left=right=0;
for(int i=n-1;i>=0;--i)
{
if(s[i]=='(')
{
left++;
}
else
{
right++;
}
if(left==right)
{
maxans=fmax(maxans,2*left);
}
else if(left>right)
{
left=right=0;
}
}
return maxans;
}六、合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
①排序求解
①取下来排序求解
这种方式比较暴力，就是全部取下来，然后排序，组建新链表。时间复杂度：0(N*logN)，空间复杂度：0(N)
int cmp(const void* x,const void* y)
{
return *(int*)x-*(int*)y;
}
struct ListNode* CreateNode(int n)
{
struct ListNode* newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
if(newnode==NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->next=NULL;
newnode->val=n;
return newnode;
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize)
{
//如果你把链表的所有数据都摘下来存到数组，然后排序
if(listsSize==0||lists==NULL)
return NULL;
int capacity=100;
int* arr=(int*)malloc(sizeof(int)*capacity);
int j=0;
for(int i=0;i<listsSize;++i)
{
struct ListNode* cur=lists[i];
while(cur)
{
arr[j++]=cur->val;
if(j==capacity)
{
capacity*=2;
int* tmp=(int*)realloc(arr,sizeof(int)*capacity);
if(tmp==NULL)
{
perror("realloc fail");
exit(-1);
}
arr=tmp;
}
cur=cur->next;
}
}
if(j==0)
return NULL;
qsort(arr,j,sizeof(int),cmp);
struct ListNode* guard=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur=guard;
for(int i=0;i<j;++i)
{
struct ListNode* newnode=CreateNode(arr[i]);
cur->next=newnode;
cur=cur->next;
}
struct ListNode* head=guard->next;
free(guard);
free(arr);
return head;
}②归并递归?
②归并递归
对于任意多个链表，我们都可以对无限二分，直到只剩一个链表，这样选出其中两个进行合并，合并为一个有序链表。比如4个链表，先选出两个合并，变成3 个链表，再任意两个合并 变成?2 个再两个合并变成1个即为所求。
对于任意两个链表合并可以使用递归实现。
struct ListNode* dfs(struct ListNode* l1,struct ListNode* l2)
{
if(l1==NULL)
return l2;
if(l2==NULL)
return l1;
if(l1->val<l2->val)
{
l1->next=dfs(l1->next,l2);
return l1;
}
l2->next=dfs(l1,l2->next);
return l2;
}
struct ListNode* TwoLists(struct ListNode**lists,int l,int r)
{
if(l==r)
return lists[l];
if(l>r)
return NULL;
int mid=l+(r-l)/2;
struct ListNode* l1=TwoLists(lists,l,mid);
struct ListNode* l2=TwoLists(lists,mid+1,r);
return dfs(l1,l2);
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize)
{
if(!listsSize)
return NULL;
return TwoLists(lists,0,listsSize-1);
}