题解 | #链表中的节点每k个一组翻转#
链表中的节点每k个一组翻转
http://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e
解题思路：
- 使用递归的思想，每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;
}
}