题解 | #链表内指定区间反转--一次遍历迭代算法#

一次遍历，迭代算法解决链表指定区间反转

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        //建立虚拟头节点，指向head，不用分开处理m==1和m!=1时的情况
        ListNode dummy=new ListNode(-1);
        dummy.next=head;
      
      //m1指向m-1的节点，初始为虚拟头节点dummy
      //cur初始指向head,表示当前节点
      //m2指向m位置的节点，初始为cur
      //i表示cur节点所在的位置，因为节点从1开始数，所以i初始为1
        ListNode m1=dummy;
        ListNode cur=head;
        ListNode m2=cur;
        int i=1;
        
      //从头遍历，直到cur指向m位置
      //每次循环依次更新m1、cur、m2
        while(i<m){
            m1=cur;
            cur = cur.next;
            m2=cur;
            i++;
        }
        
      //然后就跟迭代反转链表的操作一样了,只是循环判断条件改为i<=n
      //循环结束时，pre指向n位置，cur指向n+1位置
        ListNode pre=null;
        ListNode next=null;
        while(i<=n){
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
            i++;
        }
      
      //最后将m-1节点和m节点分别指向n和n+1,完成反转
        m1.next=pre;
        m2.next=cur;
        
        return dummy.next;
    }
}