25. K 個一組翻轉鏈表 - 力扣（LeetCode）

1.模擬法

思路

將這個過程拆解為兩個步驟，第一步將單分組的節點反轉，第二步將反轉后的鏈表加入原鏈表。

針對節點反轉很容易，參考之前的206. 反轉鏈表 - 力扣（LeetCode）

針對反轉后的鏈表加入原鏈表，我們需要該鏈表前一個節點pre，以及后面一個節點nex。

所以我們要提前將pre與nex存儲起來。

具體步驟

（1）創建哨兵節點dump，讓頭節點不再特殊。同時pre=dump為第一個需要反轉鏈表的前一個節點。

（2）判斷需要反轉的鏈表是否有k個長度，若有則繼續，若無直接輸出結果dump.next；

（3）存儲nex，pre，方便后續加入原鏈表。

（4）反轉鏈表（返回新的頭節點與尾節點），并將鏈表加入原鏈表。

（5）更新pre為tail，head為tail.next，方便下一次循環。

具體代碼

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode dump = new ListNode(0,head);ListNode pre = dump;while(head!=null){ListNode tail = pre;for(int i=0;i<k;i++){tail=tail.next;if(tail==null){return dump.next;}}ListNode nex = tail.next;ListNode[] rev = myRev(head,tail);head = rev[0];tail = rev[1];pre.next = head;tail.next=nex;pre=tail;head = tail.next;}return dump.next;}public ListNode[] myRev(ListNode n1,ListNode n2){ListNode pre1 = n2.next;ListNode end = pre1;ListNode cur = n1;while(cur!=end){ListNode next1 =cur.next;cur.next=pre1;pre1=cur;cur=next1;}ListNode[] r = {n2,n1};return r;}
}