题解 | #链表内指定区间反转#

import java.util.*;
/**
     * 本题的输入是一个listnode，和拆分的两个数字，通过两个数字把listnode进行切割成三段。
     * 解题过程将listnode看成一个数组，并进行遍历，
     * 通过两个数字对数据切割成三段，不管其中是否有数据，都切割成三段。
     * 将三段数据在拼接成一个listnode进行返回。
     * 注意：遍历原始listnode时，需要使用的是遍历后剩余节点的数据。
     */
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 反转链表中指定范围的节点。
     *
     * @param head 链表的头节点。
     * @param m 范围开始的节点索引（包含）。
     * @param n 范围结束的节点索引（包含）。
     * @return 反转指定范围后的链表头节点。
     */
    public static ListNode reverseBetween(ListNode head, int m, int n) {
        // 如果链表为空或只有一个节点，直接返回原链表
        if (head == null || head.next == null) {
            return head;
        }
        // 左侧链表第一个节点
        ListNode left = new ListNode(-1);
        // 创建虚拟节点用于分割链表-左边部分
        ListNode head1 = splitListNode(left, head, m);
        // 获取分割后的左侧链表头节点
        left = deleteFirstNode(left);

        // 中间侧链表第一个节点
        ListNode middle = new ListNode(-1);
        // 分割并获取要反转的中间部分链表
        // 分割并获取要反转的中间部分链表
        int num = 0;
        if (n - m <= 0) {
            num = 0;
        } else {
            num = n - m + 2;
        }
        ListNode head2 = splitListNode(middle, head1, num);
        // 获取中间部分链表
        middle = deleteFirstNode(middle);

        // 右侧链表第一个节点
        ListNode right = new ListNode(-1);
        // 分割并获取右侧链表
        ListNode head3 = splitListNode(right, head2, Integer.MAX_VALUE);
        // 获取右侧链表头节点，并删除第一个节点
        print(left);
        print(middle);
        print(right);
        right = deleteFirstNode(right);

        // 反转中间部分链表，并合并到左侧链表
        ListNode leftMerge = mergeTwoLists(left, reverseList(middle));
        // 将左侧链表、反转后的中间部分链表和右侧链表合并
        ListNode rightMerge = mergeTwoLists(leftMerge, right);
        // 返回合并后的链表头节点
        return rightMerge;
    }

    /**
    * 打印链表中所有节点的值。
    * @param p 链表的头节点。类型为ListNode，表示一个链表的节点。
    * 该函数没有返回值。
    */
    private static void print(ListNode p) {
        // 遍历链表，打印每个节点的值
        while (p != null) {
            System.out.println(p.val);
            p = p.next;
        }
        // 打印分隔线，以区分不同的链表打印输出
        System.out.println("------------------------");
    }

    /**
     * 反转链表。
     *
     * @param head 链表的头节点。
     * @return 反转后的链表的头节点。
     */
    public static ListNode reverseList(ListNode head) {
        // 如果链表为空或只有一个节点，直接返回头节点
        if (head == null || head.next == null) {
            return head;
        }
        ListNode temp = head.next; // 要反转的节点，从第二个节点开始
        ListNode nextNode = temp.next; // 要反转的节点的下一个节点
        head.next =
            null; // 断开头节点和要反转节点的连接，防止反转后形成环

        // 使用头插法反转链表
        while (temp != null) {
            temp.next = head;
            head = temp;
            temp = nextNode;
            if (nextNode != null) {
                nextNode = nextNode.next;
            }
        }
        return head; // 返回反转后的链表的头节点
    }

    /**
     * 删除链表的第一个节点。
     * 该方法接收一个链表的头节点，并删除该链表的第一个节点，然后返回链表的新头节点。
     *
     * @param listNode 链表的头节点。如果链表为空，则不进行任何操作并返回null。
     * @return 返回删除第一个节点后的链表的头节点。如果原链表为空，则返回null。
     */
    private static ListNode deleteFirstNode(ListNode listNode) {
        // 检查链表是否为空
        if (listNode != null) {
            // 新的头节点指向原头节点的下一个节点
            ListNode newNode = listNode.next;
            listNode.next =
                null; // 删除原链表的第一个节点，将头节点的next指针置为null
            listNode = newNode; // 更新头节点为新的头节点
        }
        return listNode; // 返回新的头节点
    }

    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //任意一跳链表为空时，直接返回另外一条链表
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        } else {
            //当前层数的返回结果，放在list1后面
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }
    }

    /**
     * 根据 n的值对listnode进行切割，切割时listnode的值是按照当前node的节点进行切割，也就是0到n为一组.
     * 比如head原始数据=0-1-2-3-4-5-6，当前指针的节点为2，那就是2之后的n个元素为返回值。
     *
     * @param head head，遍历的listnode
     * @param n    n个数
     * @return ListNode
     */
    private static ListNode splitListNode(ListNode node, ListNode head, int n) {
        ListNode currentNode = node;
        // 遍历链表，找到拆分点
        for (int i = 1; i < n; i++) {
            // 如果head为null，说明给定的n超出了链表的长度，直接退出循环
            if (head == null) {
                break;
            }
            currentNode.next = head;
            currentNode = head;
            // 移动到下一个节点
            head = head.next;
        }
        // 断开链表，形成两个独立的部分
        currentNode.next = null;
        // 返回被拆分出来的后半部分链表的头节点
        return head;
    }
}