考的最多的LeetCode hard难度算法 --- k个一组翻转链表

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

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

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

示例：

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

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

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

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

这道题虽然是hard难度，而且通过率也很高，在各种面经上也常出现，因此写下来做备忘。
其实对于链表的算法题，创建哨兵头结点+头插法这个组合就能解决绝大部分了，这道题也不例外。

另外做链表类算法题时，可以多定义几个临时变量，让自己思路清晰也能大大降低链表连接出错的概率

public ListNode reverseKGroup(ListNode head, int k) {
        ListNode myHead = new ListNode(0);

        //pre为头插法的头节点
        ListNode pre = myHead;
        //start为实际插入的节点
        ListNode start = head;
        boolean stop=false;
        for (; ; ) {
            //检查剩余是否有k个节点可以翻转，如果没有直接break
            if (start == null) break;
            ListNode check = start;
            for (int i = 0; i < k - 1; i++) {
                check = check.next;
                if (check == null){
                    stop=true;
                    break;
                }
            }
            if(stop)break;
            //头插法翻转k个一组的节点
            for (int i = 0; i < k; i++) {

                ListNode startNext = start.next;
                ListNode preNext = pre.next;
                pre.next = start;
                start.next = preNext;
                start = startNext;

            }
            //pre前进k次
            for (int i = 0; i < k; i++) {
                pre = pre.next;
            }

        }
        //把剩余不足k个的节点连接上去
        while (start != null) {
            pre.next = start;
            pre = pre.next;
            start = start.next;
        }

        return myHead.next;
    }