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

import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */


    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here

	  
	  //设置虚拟头结点，方便后续操作中链表保持完整
        ListNode dummy = new ListNode(-1);
	  //头结点指向链表第一位
        dummy.next = head;
	// pre是指虚拟头结点，cur是指当前节点，并且此时虚拟头结点保持在cur节点之前
        ListNode pre = dummy;
        ListNode cur = head;
		//遍历链表，pre和cur都循环m-1次，并且让cur指向要反转链表第一位，pre指向cur的前一位
        for (int i =0; i< m -1; i++){
            
            pre = pre.next;
            cur = cur.next;
        }
		// 此时，为了完成局部链表反转，进行 n-m 次反转操作。在每次反转操作中：
        //temp 指向 cur.next（即当前需要反转的节点）。
      //cur.next 指向 temp.next（即跳过 temp）。
      //temp.next 指向 pre.next（即将 temp 插入到 pre 和 cur 之间）。
       //pre.next 更新为 temp（即将 temp 插入到 pre 的后面）。
		// 第一次循环：12345 需要反转234， 则temp为3， cur也就是2指向4， temp也就是3指向pre.next也就是2，
	  // 将pre.next赋值为temp，1指向3 所以是13245
	  //依次就是第二次循环....

        for( int i = 0; i < n-m; i++){
            ListNode temp = cur.next;

            cur.next = temp.next;

            temp.next = pre.next;

            pre.next = temp;
        }
     // 最后，返回 dummy.next，即新链表的头节点。
        return dummy.next;
        
    }
    
    
}