前提知识：
1.画图，数据结构相关的题，画图必不可少，只要能画出来，那么后面的代码就很容易能写出来，因为将抽象的数据结构转换为直观的图画
2.引入虚拟头结点，也叫哨兵位，能够避免考虑很多边界情况
3.不要吝啬空间，如果你看到第二点的时候，如果反应是有些题也可以不用虚拟节点就能解决时，其实这就已经是有点吝啬空间的思想了，一个虚拟头结点才几个字节，根本不需要考虑，大胆创建就行了
4.快慢双指针，链表中经常且好用的方法
5.链表常用存在，创建节点，头插，尾插，其中头插是比较重要的，因为通过头插可以直接完成逆序链表的操作，而很多题目中都需要逆序链表，所以头插的操作要掌握，同时又结合虚拟头结点，那么头插起来会非常方便
题目一：
算法原理：
题意很简单，就是模拟加法的操作，只不过链表是逆序的，但是不要看是逆序的就觉得有难度，如果是正序的反而要更难一点，因为加法是从低位开始计算的，而逆序链表刚好就把低位放在了头结点，反而更好操作，而正序链表如果要进行加法，反而要先逆序再操作
思路就是用两个指针指向两个链表的头结点，然后开始往后遍历，将两数的和相加并记录在一个变量t里面，最后该位只取t的个位，然后/=10即可，而循环遍历结束条件是两个指针都为空时，且t也为0才结束，其中为什么t也要为0是解决下面这种情况
即虽然两个指针为空，但还有一个进位没有进
也是可以用虚拟头结点，直接进行加法操作后，接在虚拟头结点之后就行
代码：
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {//虚拟头结点ListNode newHead=new ListNode(0);//双指针ListNode cur1=l1,cur2=l2,cur=newHead;//记录进位int t=0;//循环遍历while(cur1!=null||cur2!=null||t!=0){//如果链表1还有值if(cur1!=null){t+=cur1.val;cur1=cur1.next;}//如果链表2还有值if(cur2!=null){t+=cur2.val;cur2=cur2.next;}//进位操作cur.next=new ListNode(t%10);cur=cur.next;t/=10;}//返回真正的头结点return newHead.next;}
}题目二：
算法原理：
题意很简单，注意不能修改原结点的值，只能通过移动结点进行修改
如果还是用之前刚学链表时的思想，那就是不创建虚拟结点，同时也吝啬空间不定义变量，还不画图的话，那就脑袋里面慢慢绕了，一不小心就绕混了
因为如果不创建虚拟结点的话，12这两个结点的操作和34之间的操作是不一样的，34这里需要1这个结点指向4，而12这里没有前面的结点，因此需要自己找头结点，导致12的时候要特殊处理，不能进入循环，而创建虚拟头结点就可以让12操作和后面一样
如果创建虚拟结点后并画图，但吝啬空间的话，那么结点交换和修改就得考虑顺序且非常乱
class Solution {public ListNode swapPairs(ListNode head) {if(head==null){return head;}ListNode newHead=new ListNode(0,head);ListNode prev=newHead,cur=head;while(cur!=null&&cur.next!=null){prev.next=cur.next;prev=cur;ListNode tmp=cur.next.next;cur.next.next=cur;cur.next=tmp;cur=tmp;}return newHead.next;}
}这循环里面的代码顺序不能乱调，且一眼看过去也很乱
而直接定义变量的话就会这样
那么逻辑就直接是
prev指向next
next指向cur
cur指向nnext
且先后顺序随便，根本不影响
然后再修改变量，这里需要注意顺序，不然会出现覆盖
非常清晰
然后讨论循环终止条件
偶数结点情况下：
可以发现，如果cur==null就终止
奇数结点情况下：
可以发现，如果next==null就终止
代码：
class Solution {public ListNode swapPairs(ListNode head) {//特殊处理空结点和单结点if(head==null||head.next==null){return head;}ListNode newHead=new ListNode(0,head);ListNode prev=newHead,cur=head,next=cur.next,nnext=next.next;while(cur!=null&&next!=null){//修改结点指向prev.next=next;next.next=cur;cur.next=nnext;//修改变量(注意顺序)prev=cur;cur=nnext;if(cur!=null){next=cur.next;}if(next!=null){nnext=next.next;}}return newHead.next;}
}题目三：
算法原理：
这道题比较综合，通过模拟可以发现，无非是将前一半链表和后一半经过逆序的链表，进行合并即可，因此就涉及到三个知识点，找链表中间结点，逆序操作，合并链表
找链表中间结点，采用快慢双指针来解决
逆序链表，采用头插来解决
合并链表，模拟操作即可
需要注意的是，找到中间结点后，要将前后两个链表之间进行切断，实现两个独立的链表，才好方便进行后面的操作
代码：
class Solution {public void reorderList(ListNode head) {if(head.next==null){return;}//找到中间结点ListNode slow=head;ListNode fast=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}//拆开链表ListNode cur=head;while(cur.next!=slow){cur=cur.next;}cur.next=null;cur=head;//逆序链表ListNode newHead=new ListNode();while(slow!=null){ListNode slowNext=slow.next;slow.next=newHead.next;newHead.next=slow;slow=slowNext;}//合并链表newHead=newHead.next;while(cur!=null&&newHead!=null){ListNode curNext=cur.next;ListNode newHeadNext=newHead.next;cur.next=newHead;if(curNext!=null){newHead.next=curNext; } cur=curNext;newHead=newHeadNext;}}
}题目四：
算法原理：
题意很简单，就是按照升序合并k个链表，而且还比较好心的帮我们把k个链表进行了升序操作
我们之前学过合并2个链表，所以最容易想到的就是暴力解法，即遍历数组，第1个链表和第2个链表合并之后，再和第3个链表合并……
时间复杂度上，假设有k个链表，每个链表长度为n
合并的时间复杂度是n(k-1)+n(k-2)……+n=O(nk^2)=O（N^3）
效率非常低，所以要换一个方法
方法一：
既然是比较大小进行排序，那么就可以借助优先级队列来实现，将每个链表的头结点都扔进去，取出堆顶元素，就是所有头结点中最小的，然后对应的那个链表就扔下一个结点进去，然后再取堆顶元素，循环往复，直到对应链表为空，则停止添加，最后当堆为空时，则合并完成
时间复杂度上，堆的操作为log级别，有k个链表，所以要比较k次，又总共有n个节点，所以时间复杂度为O（n k logk）
代码一（优先级队列）：
class Solution {public ListNode mergeKLists(ListNode[] lists) {//如果数组为空或者数组中的链表为空if(lists==null||lists.length==0){return null;}//创建一个小根堆PriorityQueue<ListNode> priorityQueue=new PriorityQueue<>((o1,o2)->o1.val-o2.val);//取出所有的头结点放进去for(ListNode node:lists){if(node!=null){priorityQueue.offer(node);}}//创建一个虚拟节点ListNode newHead=new ListNode();ListNode prev=newHead;//合并链表while(!priorityQueue.isEmpty()){ListNode cur=priorityQueue.poll();prev.next=cur;prev=cur;//如果该链表为空则不添加if(cur.next!=null){priorityQueue.offer(cur.next);}}//返回头结点return newHead.next;}
}方法二：
既然合并k个链表可以拆分为n次合并2个链表，那么子问题是一样的，就可以采用分治递归的思想，以归并排序来解决，套模板即可
代码二（分治递归）：
class Solution {public ListNode mergeKLists(ListNode[] lists) {//要求对lists数组从下标0开始到lists.length-1之间的链表进行合并并返回头结点return merge(lists,0,lists.length-1);}public ListNode merge(ListNode[] lists,int left,int right){//如果为空区间if(left>right){return null;}//如果只有一个链表，不用合并if(left==right){return lists[left];}//找到中间值，分为[left,mid],[mid+1,right]两个区间int mid=(left+right)/2;//递归处理左右两部分ListNode l1=merge(lists,left,mid);ListNode l2=merge(lists,mid+1,right);//合并两个链表ListNode newHead=new ListNode();ListNode prev=newHead;while(l1!=null&&l2!=null){if(l1.val>=l2.val){prev.next=l2;prev=l2;l2=l2.next;}else{prev.next=l1;prev=l1;l1=l1.next;}}if(l1!=null){prev.next=l1;}if(l2!=null){prev.next=l2;}//返回头结点return newHead.next;}
}题目五：
算法原理：
题意很简单，就是不停翻转长度为k的链表，直到全部翻转完或者剩余长度不够k则停止
虽然是困难题，但是模拟的操作并不难
首先我们先遍历一遍链表，统计出链表的长度，然后再除k看看有多少组需要被翻转，假设为n组
然后循环n次，每次循环代表每一组，循环里面再嵌套循环k次，表示将k个结点进行翻转
最后拼接上后面未被翻转的结点
翻转也就是逆序，所以我们采用之前用的头插法
其中需要注意的是
每次头插翻转完一组后，后面结点跟的是第一次头插的结点后面
代码：
class Solution {public ListNode reverseKGroup(ListNode head, int k) {//如果翻转长度为1，则不用翻转if(k==1){return head;}//遍历链表统计长度ListNode cur=head;int len=0;while(cur!=null){cur=cur.next;len++;}//如果长度不够k，直接返回if(len<k){return head;}int n=len/k;//头插翻转cur=head;ListNode newHead=new ListNode(0);ListNode prev=newHead;ListNode tmp=null;//翻转n组for(int i=0;i<n;i++){//记录下一组的前驱结点tmp=cur; for(int j=0;j<k;j++){ ListNode next=cur.next; cur.next=prev.next;prev.next=cur;cur=next;}//更新前驱节点prev=tmp;}//拼接剩余节点prev.next=cur;//返回头结点return newHead.next;}
}
 详解)
