力扣025 K组中的反向节点

力扣025 K组中的反向节点

题目：

给定链表的 ，一次反转列表的节点，并返回修改后的列表。head``k

k`是一个正整数，小于或等于链表的长度。如果节点数不是节点的倍数，那么最终省略的节点应保持原样。`k

您不能更改列表节点中的值，只能更改节点本身。

示例 1：

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

示例 2：

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

约束：

• 列表中的节点数为 。n
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

解题思路：

首先我们需要准备两个小函数一个用来保证分组K个,另一个用来反转这个分组中的k个节点。第二个函数用来反转这K个节点的时候一定要记录最后一个节点的下一节点好用来做连接。

代码：

public class ReverseKGroup {
    //1.定义一个节点类
    public static class ListNode {
        public int value;
        public ListNode next;
    }

    /**
     * 主函数
     * @param head
     * @param k
     * @return
     */
    public static ListNode reverseKGroup(ListNode head, int k) {
        //1.首先定义一个开始节点指向头节点
        ListNode start = head;
        //2.调用函数返回每一组最后一个节点的函数
        ListNode end = getKGroupEnd(start, k);
        //3.如果链表的节点不够K个最后一个节点为null
        if (end == null) {
            return head;
        }
        // 第一组凑齐了！

        //head抓住新头部 以后也是这个作为头部 最后返回这个头部
        head = end;
        //反转start到end
        reverse(start, end);
        // 上一组的结尾节点
        ListNode lastEnd = start;
        while (lastEnd.next != null) {
            //新一组的开始节点
            start = lastEnd.next;
            //新一组的结尾节点
            end = getKGroupEnd(start, k);
            if (end == null) {
                return head;
            }
            reverse(start, end);
            //上一节点的last指针的next指向此时这一组的end
            lastEnd.next = end;
            //上一节点的last指针指向此时这一组的start
            lastEnd = start;
        }
        //最后返回head
        return head;
    }

    /**
     * 这个函数的作用就是从链表的某一结点开始数K个节点并且返回第K个节点
     * 之所以要保证start!=null是因为要保证start不越界同时也是保证每次分组都是K个
     * @param start
     * @param k
     * @return
     */
    public static ListNode getKGroupEnd(ListNode start, int k) {
        //数够K个节点
        while (--k != 0 && start != null) {
            start = start.next;
        }
        //返回第K个节点
        return start;
    }

    /**
     * 这个函数的作用就是将每一块分组中的链表进行反转，反转的时候我们首先要记录下原本每块分组最后一个节点的下一个节点
     * 当这块链表反转完成后将刚开始的节点的下一指针连接到刚刚最后一个节点的下一节点。
     * @param start
     * @param end
     */
    public static void reverse(ListNode start, ListNode end) {
        //记录最后节点的下一个节点
        end = end.next;
        ListNode pre = null;
        ListNode cur = start;
        ListNode next = null;
        //进行链表的反转
        while (cur != end) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        //最后将刚开始的节点的next指针连接到最后节点的下一节点
        start.next = end;
    }
}