?？途W(wǎng)高頻算法題系列-BM3-鏈表中的節(jié)點每k個一組翻轉(zhuǎn)

題目描述

將給出的鏈表中的節(jié)點每 k 個一組翻轉(zhuǎn)，返回翻轉(zhuǎn)后的鏈表如果鏈表中的節(jié)點數(shù)不是 k 的倍數(shù)，將最后剩下的節(jié)點保持原樣你不能更改節(jié)點中的值，只能更改節(jié)點本身。

原題目見：BM3 鏈表中的節(jié)點每k個一組翻轉(zhuǎn)

解法一：遞歸

使用遞歸的方式處理每k個一組的結(jié)點，具體處理方式如下：

• 首先用tail記錄每次翻轉(zhuǎn)的尾部，就是第k+1個結(jié)點，從頭結(jié)點開始，遍歷鏈表，找到第k+1個結(jié)點，如果當(dāng)前結(jié)點數(shù)不夠k個，則不用反轉(zhuǎn)直接返回；
• 然后從鏈表頭開始遍歷，翻轉(zhuǎn)結(jié)點并記錄反轉(zhuǎn)后的表頭pre和表尾結(jié)點head；
• 然后遞歸處理從tail開始的后面的鏈表結(jié)點，并將head指向遞歸處理后的鏈表；
• 返回新的表頭即為反轉(zhuǎn)后的新的鏈表的表頭結(jié)點。

代碼

public class Bm003 {
    /**
     * 遞歸
     *
     * @param head ListNode類
     * @param k    int整型
     * @return ListNode類
     */
    public static ListNode reverseKGroup(ListNode head, int k) {
        // 找到每次翻轉(zhuǎn)的尾部
        ListNode tail = head;
        // 遍歷k次到尾部
        for (int i = 0; i < k; i++) {
            // 如果不足k到了鏈表尾部，直接返回，不翻轉(zhuǎn)
            if (tail == null) {
                return head;
            }
            tail = tail.next;
        }
        // 翻轉(zhuǎn)時需要的前序和當(dāng)前節(jié)點
        ListNode pre = null, cur = head;
        // 在到達(dá)當(dāng)前段尾部節(jié)點前
        while (cur != tail) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        // 當(dāng)前尾部指向下一段要翻轉(zhuǎn)的鏈表
        head.next = reverseKGroup(tail, k);
        return pre;
    }

    public static void main(String[] args) {
        ListNode head = ListNode.testCase2();
        System.out.println("翻轉(zhuǎn)之前");
        ListNode.print(head);

        // 當(dāng)k=2時
        ListNode newHead = reverseKGroup(head, 2);
        System.out.println("當(dāng)k=2時，翻轉(zhuǎn)之后");
        ListNode.print(newHead);

        ListNode head1 = ListNode.testCase2();
        // 當(dāng)k=3時
        ListNode newHead2 = reverseKGroup(head1, 3);
        System.out.println("當(dāng)k=3時，翻轉(zhuǎn)之后");
        ListNode.print(newHead2);
    }
}

相信堅持的力量！