Java 题解 | #牛群的重新排列#

该题目考察了链表的基本操作以及链表节点的反转。

链表节点的反转操作，可以使用头插法或者栈来实现。同时，需要注意对边界条件和特殊情况的处理，例如链表为空或只有一个节点的情况。

• 创建一个虚拟头节点 dummy，使其指向原链表的头节点 head。
• 然后，使用两个指针 preNode 和 curNode 分别表示左子链表的尾部节点和当前节点，初始化为 dummy 和 dummy.next。
• 将 curNode 移动到需要反转的区间的起始位置 left。
• 使用头插法将区间内的节点逐个移到 preNode 的后面，完成反转操作。
• 返回虚拟头节点 dummy 的下一个节点作为新的头节点。

该算法的时间复杂度为 O(n)，其中 n 是链表的长度。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     *
     */
    public ListNode reverseBetween (ListNode head, int left, int right) {
        // write code here
        if (head == null || head.next == null || left == right)
            return head;

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode preNode = dummy; // 左子链表的尾部节点
        ListNode curNode = dummy.next;

        // 将 curNode 移动到 left 的位置
        for (int i = 1; i < left; i++) {
            preNode = preNode.next;
            curNode = curNode.next;
        }

        ListNode tail = curNode; // 反转后的链表尾部节点

        // 使用头插法进行链表反转
        for (int i = left; i < right; i++) {
            ListNode nextNode = curNode.next;
            curNode.next = nextNode.next;
            nextNode.next = preNode.next;
            preNode.next = nextNode;
        }

        return dummy.next;
    }
}