題目
給你一個鏈表，每 k 個節(jié)點一組進行翻轉(zhuǎn)被辑，請你返回翻轉(zhuǎn)后的鏈表挽封。
k 是一個正整數(shù)已球，它的值小于或等于鏈表的長度。
如果節(jié)點總數(shù)不是 k 的整數(shù)倍，那么請將最后剩余的節(jié)點保持原有順序智亮。
示例 :
給定這個鏈表：1->2->3->4->5
當(dāng) k = 2 時退疫，應(yīng)當(dāng)返回: 2->1->4->3->5
當(dāng) k = 3 時，應(yīng)當(dāng)返回: 3->2->1->4->5
說明 :
你的算法只能使用常數(shù)的額外空間鸽素。
你不能只是單純的改變節(jié)點內(nèi)部的值褒繁，而是需要實際的進行節(jié)點交換。
思路
用的是精選題解的思路 因為有圖 整個過程解釋的非常詳細馍忽。這道題比較難 在注釋中我將每一步的作用都詳細的寫上了
image
image
源代碼
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
ListNode end = dummy;
while (end.next != null) {
for (int i = 0; i < k && end != null; i++) end = end.next;
if (end == null) break;
ListNode start = pre.next;
//提前保存下一次要反轉(zhuǎn)的鏈表部分的第一個節(jié)點
ListNode next = end.next;
//分割本次反轉(zhuǎn)與為即將將要進行反轉(zhuǎn)的元素
end.next = null;
//reverse(start)返回的是本次反轉(zhuǎn)后的最后一個節(jié)點
//pre初始為NULL pre.next = 本次反轉(zhuǎn)最后一個節(jié)點位置 為下一次反轉(zhuǎn)做準(zhǔn)備 start = pre.next 因為上面有start = pre.next 所以現(xiàn)在start的位置為反轉(zhuǎn)后部分的最后一個節(jié)點
pre.next = reverse(start);
//將反轉(zhuǎn)后最后一個節(jié)點與還未反轉(zhuǎn)部分的第一個節(jié)點相連接
start.next = next;
//為下一次反轉(zhuǎn)設(shè)置前趨節(jié)點
pre = start;
//為下一次反轉(zhuǎn)設(shè)置end節(jié)點 以便下一次反轉(zhuǎn)通過end來確定下次反轉(zhuǎn)的結(jié)束節(jié)點所在位置（那個for循環(huán)end = end.next）
end = pre;
}
return dummy.next;
}
private ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
}
return pre;
}
