題目描述
一個鏈表每 k 個節(jié)點一組進行翻轉(zhuǎn)。k 是一個正整數(shù)诊胞，節(jié)點總數(shù)不足 k 保持原有順序庸队。
示例：
輸入：1->2->3->4->5和k=3
輸出：3->2->1->4->5
解析
實現(xiàn)技巧：遞歸實現(xiàn)
實現(xiàn)方法
- 找到前k個結(jié)點（不足直接返回原鏈表）
- 反轉(zhuǎn)前k個結(jié)點產(chǎn)生反轉(zhuǎn)鏈表刁卜，記為List1
- 遞歸調(diào)用傳入第k+1個以及之后的結(jié)點組成的新鏈表得到鏈表，記為List2
- 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個結(jié)點*/
ListNode tail = head;
int i = 0;
for(; i < k && tail != null; i++){
tail = tail.next;
}
/*不足k個結(jié)點直接返回原鏈表*/
if(i < k){
return head;
}
/*反轉(zhuǎn)前k個結(jié)點產(chǎn)生反轉(zhuǎn)鏈表h*/
ListNode h = reverseList(head, tail);
/*遞歸調(diào)用傳入第k+1個以及之后的結(jié)點組成的新鏈表得到鏈表逢唤，此鏈表鏈接到h之后*/
head.next = reverseKGroup(tail, k);
return h;
}
/*鏈表反轉(zhuǎn)函數(shù)*/
private ListNode reverseList(ListNode head, ListNode tail){
/*如果鏈表少于2個結(jié)點不需要反轉(zhuǎn)*/
if(head == null || head.next == null){
return head;
}
/*定義三個引用拉讯，分別指向當前結(jié)點second，當前結(jié)點的前驅(qū)first智玻，當前結(jié)點的后繼third*/
ListNode first = null;
ListNode second = head;
ListNode third = head;
/*三引用依次后移遂唧，操作結(jié)點的next引用指向，直到當前結(jié)點second為tail停止*/
while(second != tail){
third = third.next;
second.next = first;//當前結(jié)點next指向前驅(qū)
first = second;
second = third;
}
return first;
}
總結(jié)
代碼目前在LeetCode上執(zhí)行效率最高的解法吊奢，同時也是相對比較容易想到和實現(xiàn)的解法盖彭。主要在于熟練理解遞歸算法纹烹，了解它的解題思路，遞歸表達式召边，遞歸的結(jié)束條件等等铺呵，這樣在實際解決問題中可以事半功倍。
LeetCode執(zhí)行結(jié)果截圖
