题目描述
一个链表每 k 个节点一组进行翻转。k 是一个正整数，节点总数不足 k 保持原有顺序。
示例：
输入：1->2->3->4->5和k=3
输出：3->2->1->4->5
解析
实现技巧：递归实现
实现方法
- 找到前k个结点（不足直接返回原链表）
- 反转前k个结点产生反转链表，记为List1
- 递归调用传入第k+1个以及之后的结点组成的新链表得到链表，记为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个结点*/
ListNode tail = head;
int i = 0;
for(; i < k && tail != null; i++){
tail = tail.next;
}
/*不足k个结点直接返回原链表*/
if(i < k){
return head;
}
/*反转前k个结点产生反转链表h*/
ListNode h = reverseList(head, tail);
/*递归调用传入第k+1个以及之后的结点组成的新链表得到链表，此链表链接到h之后*/
head.next = reverseKGroup(tail, k);
return h;
}
/*链表反转函数*/
private ListNode reverseList(ListNode head, ListNode tail){
/*如果链表少于2个结点不需要反转*/
if(head == null || head.next == null){
return head;
}
/*定义三个引用，分别指向当前结点second，当前结点的前驱first，当前结点的后继third*/
ListNode first = null;
ListNode second = head;
ListNode third = head;
/*三引用依次后移，操作结点的next引用指向，直到当前结点second为tail停止*/
while(second != tail){
third = third.next;
second.next = first;//当前结点next指向前驱
first = second;
second = third;
}
return first;
}
总结
代码目前在LeetCode上执行效率最高的解法，同时也是相对比较容易想到和实现的解法。主要在于熟练理解递归算法，了解它的解题思路，递归表达式，递归的结束条件等等，这样在实际解决问题中可以事半功倍。
LeetCode执行结果截图
