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

import java.util.*;

class ListNode {
    int val;
    ListNode next = null;

    public ListNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        
        // 找到反转部分的前一个节点
        for (int i = 0; i < m - 1; i++) {
            pre = pre.next;
        }
        
        // left指向反转部分的第一个节点
        ListNode left = pre.next;
        // right指向反转部分的最后一个节点
        ListNode right = left;
        
        // 移动right到反转部分的最后一个节点
        for (int i = 0; i < n - m; i++) {
            right = right.next;
        }
        
        // 记录反转部分后面的节点
        ListNode a = right.next;
        // 断开反转部分与链表的连接
        right.next = null;
        
        // 反转从left到right的部分
        reverseLink(left);
        
        // 将反转后的部分重新连接到链表中
        pre.next = right;
        left.next = a;
        
        return dummy.next;
    }

    private void reverseLink(ListNode left) {
        ListNode cur = left;
        ListNode pre = null;
        while (cur != null) {
            ListNode curn = cur.next;
            cur.next = pre;
            pre = cur;
            cur = curn;
        }
        // 反转完成后，pre指向新的头节点，left指向新的尾节点
        // 将left.next设置为pre，以便于外部方法连接反转后的链表
        left.next = pre;
    }
}