单链表区间反转

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明: 1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

实现思路

1. 反转[m,n]之间的子链表：需记录m的前一个节点，n的后一个节点
2. 反转后链表插入原链表；

涉及单链表的按索引查找元素，插入，删除操作知识

代码

public static ListNode reverseBetween(ListNode head, int m, int n) {
       ListNode dummy = new ListNode(-1);
       dummy.next = head;
       //遍历指针
       ListNode cur = dummy;
       //找到m-n之间的节点，并反转
       for (int i = 1; i < m; i++) {
           cur = cur.next;
       }
       //m的后1个节点，反转后即为尾部的前一个节点
       ListNode  last = cur.next;
       //m的前1个节点
       ListNode front= cur;
       //反转的临时变量
       ListNode pre= null;
       for (int i = m; i <= n; i++) {
           cur = front.next;
           front.next = cur.next;
           cur.next = pre;
           pre= cur;
       }
       //尾部：取n的后一个节点
       cur= front.next;
       //插入反转后的链表
       front.next = pre;
       //衔接尾部
       last.next= cur;
       return dummy.next;
   }