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

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 reverse(ListNode head){
        if(head==null||head.next==null){
            return head;
        }
        ListNode pre=null;
        ListNode next=null;
        while(head!=null){
            next=head.next;
            head.next=pre;
            pre=head;
            head=next;
        }
        return pre;     
    }
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        int index=1;//记录当前遍历到链表的哪个位置了
        ListNode pre=null;//用来记录这段区间的前一个节点
        ListNode rear=null;//用来记录这段区间的后一个节点
        ListNode start=null;//反转区间链表的头节点
        ListNode end=null;//反转区间链表的尾节点
        ListNode cur=head;
        while(cur!=null){
            if(index==m-1){
                pre=cur;    
            }
            if(index==m){
                start=cur;
            }
            if(index==n){
                end=cur;
                rear=cur.next;
                break;//遍历到第n个节点break
            }
            cur=cur.next;
            index++;
        }
        //找到这四个关键节点之后就能进行反转了
        //注意这里有个细节，如果m==1的话，此时是找不到pre节点的此时pre节点是不存在的，恰好pre初始值为null也满足这种特殊情况
        end.next=null;
        ListNode tmp=start;
        start=reverse(start);//反转链表
        if(pre!=null){
            pre.next=start;
        }
        System.out.println(tmp.val);
        tmp.next=rear;
        return pre==null?start:head;  
    }
}