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

• 1、针对只有一个节点时，或者反转区间差为0时，直接信任传入链表头节点（不对头节点判空），返回头节点

• 2、针对只有两个节点时，反转区间开始位置必定为1，且反转后，表尾成为新的表头，故需要将表头指向原表尾，返回新表头

• 3、针对多节点，反转区间差大于等于1的，首先遍历寻找到区间开始节点，保存开始节点前一个节点，用于指向反转后区间的开始节点，另外需要保存开始遍历的节点，用于反转完成后的重新连接链表后续节点，即start = cur，然后开始遍历区间，开始进行反转，反转期间，需要保存一个临时节点tnx，表示当前节点下一节点，然后将当前节点指向前一节点pre（初始为null），再将pre指向当前节点cur，最后，将当前节点指向下一节点tnx，区间索引加1，在区间结束后，重新连接区间原开始反转节点的后续节点（第一次反转时，开始节点的后续节点被置空了），此时遍历完成后当前节点为区间外后续第一个节点，即start.next = cur;

• 4、思路：

  4.1反转

  4.2重新连接

• 5、实现

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) {
        // write code here
        if(head.next == null || m == n){
            return head;
        }
        int tm = 1;
        ListNode cur = head;
        ListNode ppre = null;
        while(tm < m){
            ppre = cur;
            cur = cur.next;
            tm++;
        }
        ListNode start = cur;
        ListNode pre = null;
        while(tm <= n){
            ListNode tnx = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tnx;
            tm++;
        }
        if(ppre != null){
            ppre.next = pre;
        }
        if(m == 1){
            head = pre;
        }
        if(cur != null){
            start.next = cur;
        }
        return head;
        
    }
}
``