易错点!
一定要记住断掉下一个结点与后面的结点的连接
public class solution {
public ListNode reverseKGroup(ListNode head, int k) {
// Assumption: k > 0
// corner case
if (head == null) {
return head;
}
// case 1:如果LinkedList得长度小于k,那么不用翻转,只需要return head;
// 这里用for loop遍历了k - 1次,如果cur后面依然有ListNode,那么就继续遍历,如果没有就直接return head。
ListNode cur = head;
for (int i = 0; i < k - 1; i++) {
if (cur.next != null) {
cur = cur.next;
} else {
return head;
}
}
// 程序走到这里说明LinkedList长度比k大,可以进行翻转。
// 我们当前层要做的是把当前的K个Node翻转完并接上后面翻转好的subHead。
ListNode subHead = reverseKGroup(cur.next, k);
//重点!一定要断掉cur和后面的listNode的连接,否则答案会出现cycle
cur.next = null;
ListNode newHead = reverse(head);
head.next = subHead;
return newHead;
}
private ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
}