一、删除链表的倒数第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; }
