package com.q0025;

import com.q0203_remove_linked_list_elements.ListNode;

/**

* @author xjn

* @since 2020-06-03

* https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

* 25. K 个一组翻转链表

*/

public class Solution {

public ListNode reverseKGroup(ListNode head, int k) {

if (head == null || head.next == null) {

return head;

}

ListNode tail = head;

for (int i = 0; i < k; i++) {

if (tail == null) {

//如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

return head;

}

tail = tail.next;

}

//h

//1-->2-->3-->4-->5-->6-->7-->null

//n h

//2-->1-->3-->4-->5-->6-->7-->null

ListNode newHead = reverse(head, tail);

head.next = reverseKGroup(tail, k);

return newHead;

}

//左闭右开区间

//p c n

//1-->2--3-->4

//

private ListNode reverse(ListNode head, ListNode tail) {

ListNode pre = null;

while (head != tail) {

ListNode next = head.next;

head.next = pre;

pre = head;

head = next;

}

return pre;

}

}