题解 | #链表中的节点每k个一组翻转#
递归解决
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
* 递归解决，每k个一组
* 函数定义：将head为头结点的链表，按照k个一组反转，
* 每组只负责自己这个组的反转，递归结束条件，不够k个一组
* （注意：反转后，头变尾，尾变头）
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode reverseKGroup (ListNode head, int k) {
// write code here
ListNode ptr = head;
int i;
for(i=0; i<k-1; i++) {
if (ptr == null) {
break;
}
ptr = ptr.next;
}
//不够k-1步或者ptr为null不够k个
if (i < k-1 || ptr == null) {
return head;
}
ListNode next = ptr.next;
ptr.next = null;
reverseList(head);
//head是反转后的尾巴
head.next = reverseKGroup(next, k);
//ptr是反转后的头
return ptr;
}
//链表反转
public ListNode reverseList(ListNode head) {
ListNode res = null;
ListNode curr = head;
while(null != curr) {
ListNode next = curr.next;
curr.next = res;
res = curr;
curr = next;
}
return res;
}
}
