K 個一組翻轉鏈表

這道算法題就是鏈表多個算法思想的結合，解決這一道leetcodehot100的鏈表題至少能做一半了

大概有一下幾個點

1.鏈表定位

2.鏈表翻轉

3.哨兵節點

4.鏈表合并

看看題目

給你鏈表的頭節點?head?，每?k?個節點一組進行翻轉，請你返回修改后的鏈表。

k?是一個正整數，它的值小于或等于鏈表的長度。如果節點總數不是?k?的整數倍，那么請將最后剩余的節點保持原有順序。

你不能只是單純的改變節點內部的值，而是需要實際進行節點交換。

但說是算法思想很多，但這些個的算法難度復雜度加起來不過是o1+o1，還是o1

真正的難點是在翻轉合并之后，精準的定位到哨兵和前綴節點

這是一開始的p0，用于合并

以及pre，用于翻轉

這是一個k個鏈表翻轉后的p0（p0是指向1）與pre（pre就是2），這里區分一下

這里p0是不會動的，然后pre是一直pre=pre.next的

所以現在的pre在藍色鏈表原的最后一個，也就是翻轉后的第一個

此時藍色已經翻轉了，所以我們這里需要做兩個事情

1.將藍色與后面的連起來

2.使得后面的部分也和鏈表最開始的狀態一樣（pre和p0的位置）

? ? ? ? ListNode temp= p0.next;//記錄一下翻轉后末尾的節點，因為要用來當下一段的p0

? ? ? ? ? ? p0.next.next = cur; //將藍色和后面的連起來

? ? ? ? ? ? p0.next = pre;//將藍色部分與前面的連起來，因為p0會指向前一段的末尾

? ? ? ? ? ? p0 = temp;//使得p0指向后面的頭節點

下面直接開始做題

class Solution {public ListNode reverseKGroup(ListNode head, int k) {// 找到節點的數量nint n = 0;for (ListNode cur = head; cur != null; cur = cur.next) {n++;}//初始化前綴指針，哨兵節點ListNode dummy = new ListNode(0, head);ListNode p0 = dummy;ListNode pre = null;ListNode cur = head;for (; n >= k; n -= k) {//翻轉鏈表，翻轉后的pre是當前k個的最后一個，cur是下面k個的第一個for (int i = 0; i < k; i++) { ListNode nxt = cur.next;cur.next = pre; pre = cur;cur = nxt;}ListNode temp= p0.next;//記錄一下翻轉后末尾的節點，因為要用來當下一段的p0p0.next.next = cur; //將藍色和后面的連起來p0.next = pre;//將藍色部分與前面的連起來，因為p0會指向前一段的末尾p0 = temp;//使得p0指向后面的頭節點}return dummy.next;}
}