題目描述

一個(gè)鏈表每 k 個(gè)節(jié)點(diǎn)一組進(jìn)行翻轉(zhuǎn)。k 是一個(gè)正整數(shù)，節(jié)點(diǎn)總數(shù)不足 k 保持原有順序。

示例：
輸入：1->2->3->4->5和k=3
輸出：3->2->1->4->5

解析

實(shí)現(xiàn)技巧：遞歸實(shí)現(xiàn)

實(shí)現(xiàn)方法

1. 找到前k個(gè)結(jié)點(diǎn)（不足直接返回原鏈表）
2. 反轉(zhuǎn)前k個(gè)結(jié)點(diǎn)產(chǎn)生反轉(zhuǎn)鏈表，記為L(zhǎng)ist1
3. 遞歸調(diào)用傳入第k+1個(gè)以及之后的結(jié)點(diǎn)組成的新鏈表得到鏈表，記為L(zhǎng)ist2
4. List2鏈接到List1之后即可

代碼

private class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
public ListNode reverseKGroup(ListNode head, int k) {
    if(null == head){
        return head;
    }
    /*找到前k個(gè)結(jié)點(diǎn)*/
    ListNode tail = head;
    int i = 0;
    for(; i < k && tail != null; i++){
        tail = tail.next;
    }
    /*不足k個(gè)結(jié)點(diǎn)直接返回原鏈表*/
    if(i < k){
        return head;
    }
    /*反轉(zhuǎn)前k個(gè)結(jié)點(diǎn)產(chǎn)生反轉(zhuǎn)鏈表h*/
    ListNode h = reverseList(head, tail);
    /*遞歸調(diào)用傳入第k+1個(gè)以及之后的結(jié)點(diǎn)組成的新鏈表得到鏈表，此鏈表鏈接到h之后*/
    head.next = reverseKGroup(tail, k);
    return h;
}
/*鏈表反轉(zhuǎn)函數(shù)*/
private ListNode reverseList(ListNode head, ListNode tail){
    /*如果鏈表少于2個(gè)結(jié)點(diǎn)不需要反轉(zhuǎn)*/
    if(head == null || head.next == null){
        return head;
    }
    /*定義三個(gè)引用，分別指向當(dāng)前結(jié)點(diǎn)second，當(dāng)前結(jié)點(diǎn)的前驅(qū)first，當(dāng)前結(jié)點(diǎn)的后繼third*/
    ListNode first = null;
    ListNode second = head;
    ListNode third = head;
    /*三引用依次后移，操作結(jié)點(diǎn)的next引用指向，直到當(dāng)前結(jié)點(diǎn)second為tail停止*/
    while(second != tail){
        third = third.next;
        second.next = first;//當(dāng)前結(jié)點(diǎn)next指向前驅(qū)
        first = second;
        second = third;
    }
    return first;
}

總結(jié)

代碼目前在LeetCode上執(zhí)行效率最高的解法，同時(shí)也是相對(duì)比較容易想到和實(shí)現(xiàn)的解法。主要在于熟練理解遞歸算法，了解它的解題思路，遞歸表達(dá)式，遞歸的結(jié)束條件等等，這樣在實(shí)際解決問題中可以事半功倍。

LeetCode執(zhí)行結(jié)果截圖