解题思路:
-
使用递归的思想,每K个数进行一次递归,如果最后剩的数少于k个,那么提前将当前阶段的head返回。
-
每轮递归过程,都将本轮K的进行reverse,但是需要指明链表反转的起始位置和结束位置。
-
将反转后链表的尾节点指向 递归的下一轮。
-
返回反转之后的头结点即可!
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode reverseKGroup (ListNode head, int k) {
if(head == null){
return null;
}
ListNode cur = head;
for(int i=0; i<k; i++){
if(cur == null){
return head;
}
cur = cur.next;
}
ListNode new_head = reverse(head, cur);
head.next = reverseKGroup(cur, k);
return new_head;
}
//规定好链表反转的起始和结束位置,这样可以避免截断
public ListNode reverse(ListNode head, ListNode last){
ListNode pre = null, cur = head;
while(cur != last){
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}