題目

這其實(shí)是一道變形的鏈表反轉(zhuǎn)題，大致描述如下

給定一個(gè)單鏈表的頭節(jié)點(diǎn) head,實(shí)現(xiàn)一個(gè)調(diào)整單鏈表的函數(shù)，使得每K個(gè)節(jié)點(diǎn)之間為一組進(jìn)行逆序，并且從鏈表的尾部開始組起，頭部剩余節(jié)點(diǎn)數(shù)量不夠一組的不需要逆序。（不能使用隊(duì)列或者棧作為輔助）

例如： 鏈表:1->2->3->4->5->6->7->8->null, K = 3。那么 6->7->8，3->4->5，1->2各位一組。調(diào)整后：1->2->5->4->3->8->7->6->null。其中 1，2不調(diào)整，因?yàn)椴粔蛞唤M。

解答

這道題的難點(diǎn)在于，是從鏈表的尾部開始組起的，而不是從鏈表的頭部，如果是頭部的話，那我們還是比較容易做的，因?yàn)槟憧梢员闅v鏈表，每遍歷 k 個(gè)就拆分為一組來逆序。但是從尾部的話就不一樣了，因?yàn)槭菃捂湵恚荒芡蟊闅v組起。

先做一道類似的反轉(zhuǎn)題

在做這道題之前，我們不仿先來看看如果從頭部開始組起的話，應(yīng)該怎么做呢？例如：鏈表:1->2->3->4->5->6->7->8->null, K = 3。調(diào)整后：3->2->1->6->5->4->7->8->null。其中 7，8不調(diào)整，因?yàn)椴粔蛞唤M。

對(duì)于這道題，如果你不知道怎么逆序一個(gè)單鏈表，那么可以看一下我之前寫的https://blog.csdn.net/wudawei071193/article/details/99286615

這道題我們可以用遞歸來實(shí)現(xiàn)，假設(shè)方法reverseKNode()的功能是將單鏈表的每K個(gè)節(jié)點(diǎn)之間逆序(從頭部開始組起的哦);reverse()方法的功能是將一個(gè)單鏈表逆序。

那么對(duì)于下面的這個(gè)單鏈表，其中 K = 3。

我們把前K個(gè)節(jié)點(diǎn)與后面的節(jié)點(diǎn)分割出來：

temp指向的剩余的鏈表，可以說是原問題的一個(gè)子問題。我們可以調(diào)用reverseKNode()方法將temp指向的鏈表每K個(gè)節(jié)點(diǎn)之間進(jìn)行逆序。再調(diào)用reverse()方法把head指向的那3個(gè)節(jié)點(diǎn)進(jìn)行逆序，結(jié)果如下：

接著，我們只需要把這兩部分給連接起來就可以了。最后的結(jié)果如下：

代碼如下：

    //k個(gè)為一組逆序
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode temp = head;
        for (int i = 1; i < k && temp != null; i  ) {
            temp = temp.next;
        }
        //判斷節(jié)點(diǎn)的數(shù)量是否能夠湊成一組
        if(temp == null)
            return head;

        ListNode t2 = temp.next;
        temp.next = null;
        //把當(dāng)前的組進(jìn)行逆序
        ListNode newHead = reverseList(head);
        //把之后的節(jié)點(diǎn)進(jìn)行分組逆序
        ListNode newTemp = reverseKGroup(t2, k);
        // 把兩部分連接起來
        head.next = newTemp;
        
        return newHead;
    }
    
    //逆序單鏈表
    private static ListNode reverseList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode result = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return result;
    }
復(fù)制代碼

回到本題

這兩道題可以說是及其相似的了，只是一道從頭部開始組起，這道從頭部開始組起的，也是 leetcode 的第 25 題。而面試的時(shí)候，經(jīng)常會(huì)進(jìn)行變形，例如這道字節(jié)跳動(dòng)的題，它變成從尾部開始組起，可能你一時(shí)之間就不知道該怎么弄了。當(dāng)然，可能有人一下子就反應(yīng)出來，把他秒殺了。

其實(shí)這道題很好做滴，你只需要先把單鏈表進(jìn)行一次逆序，逆序之后就能轉(zhuǎn)化為從頭部開始組起了，然后按照我上面的解法，處理完之后，把結(jié)果再次逆序即搞定。兩次逆序相當(dāng)于沒逆序。

例如對(duì)于鏈表（其中 K = 3）

我們把它從尾部開始組起，每 K 個(gè)節(jié)點(diǎn)為一組進(jìn)行逆序。步驟如下

1、先進(jìn)行逆序

逆序之后就可以把問題轉(zhuǎn)化為從頭部開始組起，每 K 個(gè)節(jié)點(diǎn)為一組進(jìn)行逆序。

2、處理后的結(jié)果如下

3、接著在把結(jié)果逆序一次，結(jié)果如下

代碼如下

public ListNode solve(ListNode head, int k) {
    // 調(diào)用逆序函數(shù)
    head = reverse(head);
    // 調(diào)用每 k 個(gè)為一組的逆序函數(shù)（從頭部開始組起）
    head = reverseKGroup(head, k);
    // 在逆序一次
    head = reverse(head);
    return head;
    
}
復(fù)制代碼

類似于這種需要先進(jìn)行逆序的還要兩個(gè)鏈表相加，這道題字節(jié)跳動(dòng)的筆試題也有出過，如下圖的第二題

這道題就需要先把兩個(gè)鏈表逆序，再節(jié)點(diǎn)間相加，最后在合并了。