題目

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

示例 :

給定這個(gè)鏈表：1->2->3->4->5

當(dāng) k = 2 時(shí)，應(yīng)當(dāng)返回: 2->1->4->3->5

當(dāng) k = 3 時(shí)，應(yīng)當(dāng)返回: 3->2->1->4->5

說明 :

• 你的算法只能使用常數(shù)的額外空間。

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

思路

用的是精選題解的思路 因?yàn)橛袌D 整個(gè)過程解釋的非常詳細(xì)。這道題比較難 在注釋中我將每一步的作用都詳細(xì)的寫上了

image

image

源代碼

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode pre = dummy;
    ListNode end = dummy;

    while (end.next != null) {
        for (int i = 0; i < k && end != null; i++) end = end.next;
        if (end == null) break;
        ListNode start = pre.next;
        //提前保存下一次要反轉(zhuǎn)的鏈表部分的第一個(gè)節(jié)點(diǎn)
        ListNode next = end.next;
        //分割本次反轉(zhuǎn)與為即將將要進(jìn)行反轉(zhuǎn)的元素
        end.next = null;
        //reverse(start)返回的是本次反轉(zhuǎn)后的最后一個(gè)節(jié)點(diǎn)
        //pre初始為NULL pre.next = 本次反轉(zhuǎn)最后一個(gè)節(jié)點(diǎn)位置 為下一次反轉(zhuǎn)做準(zhǔn)備 start = pre.next 因?yàn)樯厦嬗衧tart = pre.next 所以現(xiàn)在start的位置為反轉(zhuǎn)后部分的最后一個(gè)節(jié)點(diǎn)
        pre.next = reverse(start);
        //將反轉(zhuǎn)后最后一個(gè)節(jié)點(diǎn)與還未反轉(zhuǎn)部分的第一個(gè)節(jié)點(diǎn)相連接
        start.next = next;
        //為下一次反轉(zhuǎn)設(shè)置前趨節(jié)點(diǎn)
        pre = start;
        //為下一次反轉(zhuǎn)設(shè)置end節(jié)點(diǎn) 以便下一次反轉(zhuǎn)通過end來確定下次反轉(zhuǎn)的結(jié)束節(jié)點(diǎn)所在位置（那個(gè)for循環(huán)end = end.next）
        end = pre;
    }
    return dummy.next;
}

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