Leetcode25 K个一组反转链表

问题描述

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

在leetcode中有关反转链表的题目有206反转链表、92反转链表II、143重排链表、234回文链表
这道题的解决也依赖于上面这些问题的反转链表的技巧
这道题的特殊之处在于需要确定反转的部分，以及记录反转后链表的相对位置
可以使用边遍历边计数的方式，当计数i%k 为0时，代表遍历了k个节点，可以将这部分反转了
同时用两个指针记录反转的前一个位置m和后一个位置n
反转的过程中也需要遍历链表，当遍历到n时结束反转

以上面这个链表为例，k = 2
cur指针指向当前遍历的位置，i代表计数，记录反转部分的前一个结点startNode为start
让i从1开始，从start.next开始遍历

i = 1,i%k = 1,继续循环i++
i = 2,i%k = 0,开始反转
用next指针记录反转部分的后一个节点3

此时，cur指向2，令cur指向startNode的后继结点1，这个节点是反转部分的开始结点也将成为反转部分的尾结点

反转，cur始终指向1

为下一次循环做准备，重新指定startNode（下一次反转部分的前一个结点），它是本次反转的尾结点cur也就是结点 1 再令cur指向下一个节点3，i++

i=3 i%k = 1 继续循环 i++
i = 4 i%k = 0 开始反转
next指向反转部分的下一个节点，也就是cur的下一个节点5

cur指向startNode的下一个节点，它将作为反转部分的开始结点，反转结果的尾结点

反转，cur始终指向3

为下一次反转做准备，startNode指向cur
cur指向下一个节点，i++

i = 5,i%k = 1,继续循环i++
cur = null,结束循环
返回start.next

代码

private ListNode reverse(ListNode head, ListNode next) {
        if (head == null) {
            return head;
        }
        ListNode start = new ListNode();
        start.next = head;
        ListNode startNode = head;
        ListNode nextNode = head.next;
        while (nextNode != next) {
            startNode.next = nextNode.next;
            nextNode.next = start.next;
            start.next = nextNode;
            nextNode = startNode.next;
        }
        return start.next;
    }
    public ListNode reverseKGroup(ListNode head, int k) {
        int i = 1;
        ListNode start = new ListNode();
        ListNode startNode = start;
        start.next = head;
        ListNode cur = start.next;
        while (cur != null) {
            if (i % k == 0) {
                ListNode next = cur.next;
                cur = startNode.next;
                startNode.next = reverse(cur, next);
                startNode = cur;
            }
            i ++;
            cur = cur.next;
        }
        return start.next;
    }