K 個一組翻轉連結清單(leetcode24,25)題解

題目25，24：

給你一個連結清單，每 k 個節點一組進行翻轉，請你傳回翻轉後的連結清單。

k 是一個正整數，它的值小于或等于連結清單的長度。

如果節點總數不是 k 的整數倍，那麼請将最後剩餘的節點保持原有順序。

示例 :

給定這個連結清單：1->2->3->4->5

當 k = 2 時，應當傳回: 2->1->4->3->5

當 k = 3 時，應當傳回: 3->2->1->4->5

說明 :

你的算法隻能使用常數的額外空間。

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

題解：

這個題在leetcode屬于困難型，對于這個題的解法可以這樣想：

首先，對一個連結清單的翻轉我們肯定很熟悉，那麼k個一組不就是翻轉k個連結清單嘛，不過是翻轉之前需要将未翻轉的标記一下next，翻轉了過後再将第一個連結清單的尾節點start.next = next，然後在循環進行下一個連結清單的翻轉，直接将翻轉封裝成一個方法reverse（ListNode start）。在翻轉的時候為了讓頭節點也有前驅，我們自己定義一個headHead，如圖所示：

一次翻轉結束，更新pre end，start，end進行下一次翻轉，如果end為到達指定的長度就結束了，說明節點數不夠了嘛，然後就不用翻轉了。整個操作空間複雜度O（1），常數額外空間，時間複雜度O（n*k），在題解中還看到一種優化說不用判斷最後一個連結清單的長度，直接翻轉就完了，如果最後發現長度不夠再翻轉回來，各位可以試試。

給出我的結果以及代碼：

public ListNode reverseKGroup(ListNode head, int k) {
	//如果為空，或者隻有一個節點，直接傳回嘛
        if (head == null || head.next == null){
                return head;
        }

//給頭節點一個前驅，不用單獨為頭節點考慮了
        ListNode headHead = new ListNode(-1);
        headHead.next = head;
        ListNode pre = headHead;
        ListNode end = headHead;
        while (end.next != null){
            //end移動到末尾
            for (int i = 0; i <k&&end!=null ; i++) {
                end = end.next;
            }
            if (end == null){
                break;
            }
            ListNode start = pre.next;
            ListNode next = end.next;
            end.next = null;
            //翻轉連結清單，将頭連接配接到上一個連結清單的末尾
            pre.next = reverse(start);
            //末尾要連接配接到下一個連接配接的next，
            start.next = next;
            pre = start;
            end = start;
        }
        return headHead.next;
    }


    //翻轉連結清單
    private ListNode reverse(ListNode start) {
        if (start == null || start.next == null){
            return start;
        }
        ListNode p = start;
        ListNode q = start.next;
        while (q != null){
            ListNode t = q.next;
            q.next = p;
            p = q;
            q = t;
        }
        start.next = null;
        return p;
    }```