【链表】Leetcode 25. K 个一组翻转链表【困难】

K 个一组翻转链表

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

示例1：
在这里插入图片描述
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

解题思路

1、这个问题可以通过迭代的方式来实现，遍历链表并每 k 个节点一组进行翻转。
2、需要注意的是，我们需要记录每个翻转段的起始节点和结束节点，以便连接上一段和下一段。

具体步骤

1、定义一个辅助的虚拟头节点 dummyHead，指向链表的头部。
2、初始化两个指针 start 和 end，分别表示每个翻转段的起始和结束节点。
3、使用一个循环，每次迭代对当前翻转段进行翻转。在循环中：
（1）计算当前翻转段的长度是否达到 k。如果不足 k，则直接返回结果，因为剩余的节点不需要翻转。

（2）对当前翻转段进行翻转。翻转后，将翻转段的起始节点（翻转后的最后一个节点）连接到上一个翻转段的结束节点，将翻转后的最后一个节点（翻转前的起始节点）连接到下一个翻转段的起始节点。

（3）更新 start 和 end 指针，继续下一段的翻转。

Java实现

public class ReverseKGroup {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        //每一段的起始和结束节点
        ListNode start = dummyHead;
        ListNode end = dummyHead;

        while (end.next != null) {
            // 计算当前翻转段的长度
            for (int i = 0; i < k && end != null; i++) {
                end = end.next;
            }

            // 如果当前翻转段长度不足 k，直接返回
            if (end == null) {
                break;
            }

            // 记录翻转段的起始节点和下一段的起始节点
            ListNode nextSegment = end.next;
            ListNode segmentStart = start.next;

            // 断开当前翻转段与下一段的连接
            end.next = null;

            // 翻转当前翻转段
            start.next = reverseList(segmentStart);

            // 将翻转后的最后一个节点连接到下一段的起始节点
            segmentStart.next = nextSegment;

            // 更新 start 和 end 指针为下一段的起始节点
            //注意边界值！这里是用的第一段的末节点segmentStart。
            //不是用的下一段的起点，因为一开始我们用的是dummyHead而不是用的head
            //在for循环中 i = 0开始的
            start = segmentStart;
            end = segmentStart;
        }

        return dummyHead.next;
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;

        while (current != null) {
            ListNode nextNode = current.next;
            current.next = prev;
            prev = current;
            current = nextNode;
        }

        return prev;
    }

    public static void main(String[] args) {
        // 构造链表 1 -> 2 -> 3 -> 4 -> 5->6->7
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(6);
        head.next.next.next.next.next.next = new ListNode(7);

        int k = 3;

        // 调用 reverseKGroup 方法翻转链表
        ReverseKGroup solution = new ReverseKGroup();
        ListNode result = solution.reverseKGroup(head, k);

        // 打印翻转后的链表
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
        // 输出：2 -> 1 -> 4 -> 3 -> 5
    }
}