K 个一组翻转链表

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group

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

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

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

示例 :

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

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

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

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

思路：以K为一组切割链表，依次进行翻转，最后合并成一个大的链表。
Java代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null || head.next == null)
            return head;
        //计算链表长度，如果长度等于k，就直接翻转链表返回即可
        int length = 0;
        ListNode tmp = head;
        while(tmp != null){
            length++;
            tmp = tmp.next;
        }
        if(length == k)
            return reverse(head);
        List<ListNode> list = new ArrayList<>();
        ListNode tmpHead = head;
        ListNode split = split(tmpHead, k);
        while (split != null){
            //split不为null 说明可以一直切割下去
            ListNode reverse = reverse(tmpHead);//翻转链表
            list.add(reverse);
            tmpHead = split;
            split = split(tmpHead,k);
            if(split == tmpHead){
                list.add(reverse(split));
                break;
            }
        }
        if(split == null)
            list.add(tmpHead);
        return merge(list);
    }

    /**
     * 合并链表
     * @param list
     * @return
     */
    private ListNode merge(List<ListNode> list){
        ListNode ans = new ListNode(0);
        ListNode cur = ans;
        for (ListNode listNode : list){
            cur.next = listNode;
            ListNode last = listNode;
            while (last.next != null){
                last = last.next;
            }
            cur = last;
        }
        return ans.next;
    }

    /**
     * 切分链表
     * @param head 原链表
     * @param count 切割的长度
     * @return  返回切割后第二部分的头结点 如果为null说明长度不够切割
     */
    private ListNode split(ListNode head,int count){
        //1->2->3->4->5             2
        int i = 1;
        ListNode cur = head;
        while(i != count){
            if (cur.next == null){
                break;
            }
            cur = cur.next;
            i++;
        }
        if(cur.next == null && i == count){
            return head;
        }
        ListNode ans = cur.next;
        cur.next = null;
        return ans;
    }

    private ListNode reverse(ListNode head){
        //1->2->3->4
        ListNode cur = head.next;
        ListNode pre = head;
        head.next = null;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}