系统学习算法：专题十四 链表

前提知识：

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;}
}