前言

提示：沒有人天生就喜歡一種氣味而討厭另一種氣味。文明的暗示而已。

鏈表反轉(zhuǎn)|K個(gè)一組翻轉(zhuǎn)鏈表

給你鏈表的頭節(jié)點(diǎn) head ，每 k 個(gè)節(jié)點(diǎn)一組進(jìn)行翻轉(zhuǎn)，請(qǐng)你返回修改后的鏈表。

k 是一個(gè)正整數(shù)，它的值小于或等于鏈表的長(zhǎng)度。如果節(jié)點(diǎn)總數(shù)不是 k 的整數(shù)倍，那么請(qǐng)將最后剩余的節(jié)點(diǎn)保持原有順序。

你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際進(jìn)行節(jié)點(diǎn)交換。

進(jìn)階：你可以設(shè)計(jì)一個(gè)只用 O(1) 額外內(nèi)存空間的算法解決此問題嗎？

思路來的很快，重點(diǎn)是代碼層面的編寫，這個(gè)很重要，思路呢？就是常見的頭插法和穿針引線法來處理數(shù)組反轉(zhuǎn)問題，當(dāng)然今天我們也是采用這兩種方法解決的，那就開始實(shí)現(xiàn)他吧??

解題方法：

頭插法處理：

頭插法重點(diǎn)在理解虛擬節(jié)點(diǎn)上，如果這個(gè)問題解決了，相比較而言要比穿針引線要好實(shí)現(xiàn)的多??， 我們?cè)囍焰湵碚w分為3段，一段是已經(jīng)翻轉(zhuǎn)的，一端是正在反轉(zhuǎn)，一端是未反轉(zhuǎn)的。為了方便翻轉(zhuǎn)，我們需要京鏈表遍歷一邊，統(tǒng)計(jì)一下鏈表的長(zhǎng)度len，然后將鏈表進(jìn)行分組n=len/k,接下來就是循環(huán)進(jìn)行分組翻轉(zhuǎn)鏈表。 我們嘗試這畫一些圖，能夠更有里的說明：

結(jié)假設(shè)我們開始翻轉(zhuǎn) 4 節(jié)點(diǎn)：

具體思路：

1. 找到鏈表的長(zhǎng)度 len 分組
2. cur.next = cur.next.next; next.next = pre.next; pre.next = next;
3. 循環(huán)下一次

上代碼??

	/**
     * 方法2：頭插法
     *
     * @param head
     * @param k
     * @return
     */
    public static ListNode reverseKGroup2(ListNode head, int k) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode cur = head;
        int len = 0;
        while (cur != null) {
            cur = cur.next;
            len++;
        }
        int n = len / k; // 計(jì)算出來分幾組
        ListNode pre = dummyNode;
        cur = head;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < k - 1; j++) {  // ？ k - 1  畫圖就知道了
                ListNode next = cur.next;
                cur.next = cur.next.next;
                next.next = pre.next;
                pre.next = next;
            }
            pre = cur;  
            cur = cur.next;   // 記得修改指針
        }
       return dummyNode.next;
    }

穿針引線法處理：

這個(gè)思路可以回顧一下穿針引線，到底是怎么回事??

首先還是將鏈表分組翻轉(zhuǎn)， 我們就可以一組一組的處理，把他們分成已經(jīng)翻轉(zhuǎn)的、正在翻轉(zhuǎn)的和未翻轉(zhuǎn)的三部分，同時(shí)為了方便處理頭節(jié)點(diǎn)，我們使用了一個(gè)虛擬的節(jié)點(diǎn)。

接下來就是遍歷，根據(jù)k個(gè)為一組找到四個(gè)關(guān)鍵位置，并使用變量per，start，end，next標(biāo)記，比如下面的圖：

接著我們就開始翻轉(zhuǎn)，對(duì)應(yīng)顏色進(jìn)行翻轉(zhuǎn)，我們將end.next = null ,直接使用鏈表翻轉(zhuǎn)，復(fù)用鏈表翻轉(zhuǎn)的常規(guī)操作。??注意指針的變化，head便是傳入方法的參數(shù)，我們接著看圖：

當(dāng)然翻轉(zhuǎn)之后，我們接下來就是將原始鏈表縫起來，這就需要調(diào)整指針域，同樣這里也要注意指針的變化??

接著調(diào)整指針進(jìn)行下一次循環(huán)：

總結(jié)一下??

1. 遍歷找到四個(gè)關(guān)鍵位置，復(fù)用常規(guī)翻轉(zhuǎn)鏈表
2. pre.next = end; start.next = next; 調(diào)整指針域
3. 調(diào)整下一次循環(huán)

了解上面的圖，代碼應(yīng)該也會(huì)寫吧??

 /**
     * 方法1: 穿針引線法
     *
     * @param head
     * @param k
     * @return
     */
    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        ListNode end = dummyNode;
        while (end.next != null) { // 最終結(jié)束的地方
            for (int i = 0; i < k && end != null; i++) {
                end = end.next; // 找到當(dāng)前分組的最后一個(gè)
            }
            if (end == null) {
                break;
            }
            // 找到start next
            ListNode start = pre.next;
            ListNode next = end.next;
            end.next = null; // 思考？
            pre.next = reverse(start);
            start.next = next;
            pre = end;

            // 調(diào)整下一次循環(huán)
            end = pre;
        }
        return dummyNode.next;
    }

復(fù)習(xí)一下鏈表反轉(zhuǎn)??：

 private static ListNode reverse(ListNode head) {
       ListNode pre = null;
       ListNode cur = head;
       while(cur != null) {
           ListNode next = cur.next;
           cur.next = pre;
           pre = cur;
           cur = next;
       }
       return pre;
    }

總結(jié)

注意：指針域的變化，多畫圖更容易理解，鏈表反轉(zhuǎn)重點(diǎn)，重點(diǎn)，重點(diǎn)?。?！文章來源地址http://www.zghlxwxcb.cn/news/detail-634014.html

到了這里，關(guān)于算法通過村第二關(guān)-鏈表黃金筆記|K個(gè)一組反轉(zhuǎn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！