前提知識：

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