题解 | #链表中的节点每k个一组翻转#

package com.hhdd;

/**
 * 将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
 * 如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
 * 你不能更改节点中的值，只能更改节点本身。
 *
 * @Author huanghedidi
 * @Date 2022/7/22 22:10
 */
public class 链表中的节点每k个一组翻转 {


    public static void main(String[] args) {
        ListNode head = new ListNode(5).setNext(4).setNext(3).setNext(2).setNext(1);
        head = reverseKGroup(head, 5);
        ListNode.print(head);
    }

    /**
     * @param head ListNode类
     * @param k    int整型
     * @return ListNode类
     */
    public static ListNode reverseKGroup(ListNode head, int k) {
        // write code here
        if (head == null || head.next == null || k == 1) {
            return head;
        }
        // 搞个虚拟的头节点吧，简化处理
        ListNode headPre = new ListNode(0);
        headPre.next = head;
        int i = 1;
        // 反转区间段开头
        ListNode cur1 = head;
        // 反转区间段结尾
        ListNode cur2 = cur1;
        // 反转区间的前面一个节点
        ListNode cur3 = headPre;
        // 反转区间后面一个节点
        ListNode cur4 = null;

        while (cur2 != null) {
            if (i % k == 0) {
                // 该反转了
                cur4 = cur2.next;
                reverse(cur1, cur2);
                cur3.next = cur2;
                cur3 = cur1;
                cur1.next = cur4;
                cur1 = cur1.next;
                cur2 = cur1;
            } else {
                cur2 = cur2.next;
            }
            i++;
        }
        return headPre.next;
    }

    public static void reverse(ListNode head, ListNode tail) {
        if (head == null || tail == null || head == tail) {
            return;
        }
        ListNode cur1 = head;
        ListNode cur2 = head.next;
        cur1.next = null;
        ListNode end = tail.next;
        while (cur2 != end) {
            ListNode tmp = cur2.next;
            cur2.next = cur1;
            cur1 = cur2;
            cur2 = tmp;
        }
    }

}