1.反转链表

• 普通方法

#include 
class Solution {
public:ListNode* ReverseList(ListNode* pHead) {ListNode *cur=pHead; //当前指针ListNode * tail=nullptr;  //尾指针
ListNode* tmp; //保存指向，防止找不到
while(cur) //一直遍历到链表尾
{  tmp=cur->next;  //首先保存下一个位置的指向cur->next=tail; //反转tail=cur; //tail往后走cur=tmp; //cur向后走，不能先写tail=cur要不然cur就丢了}return tail;  }
};

• 递归

class Solution {
public:ListNode* ReverseList(ListNode* pHead) {
if(!pHead||!pHead->next) return pHead;  //如果节点为空或者next为空 此时的返回值是最后一个节点
ListNode* tail=ReverseList(pHead->next);//tail接收最后一个节点，也就是结果链表的第一个节点
//pHead->next->next=pHead; //pHead->next是尾节点，把当前节点pHead挂到尾节点的后面
//pHead->next=nullptr; //当前节点指向置空
//return tail; //返回反转链表的第一个节点
pHead->next->next=pHead;
pHead->next=nullptr;
return tail;
};
};

在第一次归的时候，pHead->next 和 tail是相同的，都是结果链表的头结点，也是反转链表的第一个节点，那么为什么不写成tail->next =pHead 因为tail始终都是结果链表最后一个节点，所以他的next永远都是结果链表第二个节点，写成这样就直接永远输出两个节点

但是写成pHead->next->next，由于pHead在改变，才能正确连接

2. 指定区间的翻转

不知道这个题难度怎么样，我写了很久，最后总结了别人的代码写出我的理解

•  头插入

翻转区间是m=2，n=4,

把cur移动到第二个节点（也就是m位置），同时保存cur前一个节点pre

每次头插的是cur->next 

1 2 3 4 5（cur->next=3,把3头插到3 2 4的最前面，其余顺移） ——> 1 3 2 4 5（cur->next=4） ——> 1 4 3 2 5

  注意：万一m=1，那么pre需要一个哨兵位安放

 ListNode* reverseBetween(ListNode* head, int m, int n) {ListNode* res=new ListNode(-1);  //设置哨兵位，防止pre越界res->next=head;  //哨兵位和链表连上ListNode* pre=res; ListNode*cur=head;for(int i=1;inext;}                    //cur在m个节点上，pre是他前一个节点for(int i=m;inext;cur->next=tmp->next;tmp->next=pre->next;pre->next=tmp;}return res->next;}
};

3.k个一组反转链表

其实k个一组是不是也是指定区间的反转！！！！！

class Solution {
public:/*** * @param head ListNode类 * @param k int整型 * @return ListNode类*/ListNode* reserve(ListNode* head,int m,int n)  //m-n区间反转{ListNode* res=new ListNode(-1);res->next=head;ListNode* cur=head;ListNode* pre=res;for(int i=1;inext;}for(int i=m;inext;cur->next=tmp->next;tmp->next=pre->next;pre->next=tmp;}return res->next;}ListNode* reverseKGroup(ListNode* head, int k) {  // write code hereif(!head) return head; //空直接返回int m=1,n=k;
ListNode* cur=head;
int size=0;  //计算节点个数while(cur){cur=cur->next;size++;} if(k>size) return head;  //k比节点总数多直接不反转head= reserve(head,m,n); //肯定反转一次m+=k;n+=k;while(n<=size) //迭代{head= reserve(head,m,n);m+=k;n+=k;}return head;}
};

4.合并有序链表

直接默写没什么好说的

class Solution {
public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {ListNode* cur1=pHead1;ListNode*cur2=pHead2;ListNode* newhead=new ListNode(-1);ListNode* cur=newhead;while(cur1&&cur2){ListNode* tmp1=cur1->next;ListNode*tmp2=cur2->next;if(cur1->valval){cur->next=cur1;cur1=tmp1;}else {cur->next=cur2;cur2=tmp2;}cur=cur->next;}while(cur1){cur->next=cur1;cur=cur->next;cur1=cur1->next;}while(cur2){cur->next=cur2;cur=cur->next;cur2=cur2->next;}return newhead->next;}
};

5.合并k个已排序的链表

感觉看到了之前k个一组反转链表

直接复用

class Solution {
public:ListNode* merge(ListNode*head1,ListNode*head2){ListNode* newhead=new ListNode(-1);ListNode*cur=newhead;ListNode*cur1=head1;ListNode*cur2=head2;while(cur1&&cur2){ListNode*tmp1=cur1;ListNode* tmp2=cur2;if(cur1->valval){cur->next=cur1;cur1=cur1->next;}else{cur->next=cur2;cur2=cur2->next;}cur=cur->next;}while(cur1){cur->next=cur1;cur1=cur1->next;cur=cur->next;}while(cur2){cur->next=cur2;cur2=cur2->next;cur=cur->next;}return newhead->next;}ListNode *mergeKLists(vector &lists) {if(lists.size()==0)return nullptr;   ListNode* newhead=lists[0];for(int i=1;i