LeetCode/25. K 个一组翻转链表

25. K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

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

示例 ：

给你这个链表：1->2->3->4->5

当k = 2时，应当返回: 2->1->4->3->5

当 k = 3时，应当返回: 3->2->1->4->5

说明：

• 你的算法只能使用常数的额外空间。
• 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

上次介绍过使用递归的方式反转链表，这次使用递归的思想，具体就是使用三个指针来进行操作，这个左程云大佬也讲过，然后就是将反转过的链表段通过递归链接起来即可。

具体代码如下：

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;

        ListNode begin, end;
        begin = end = head;
      	//寻找需要反转的区间，如果区间内结点个数不足k，则按照原来的顺序返回
        for (int i = 0; i < k; i++) {
            if (end == null) return head;
            end = end.next;
        }

      	//反转过后，last为头结点，begin为尾结点
        ListNode last = reverse(begin, end);
        begin.next = reverseKGroup(end, k);
        return last;
    }

  	//反转指定区间中的链表
    private ListNode reverse(ListNode a, ListNode b) {
        ListNode  pre, curr, next;
        pre = null;
        curr = a;
        next = a;

        while (curr != b) {
            next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }
}