/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
         ListNode res = new ListNode(-1);
         res.next = head;
         
         ListNode pre = res;
         // 移动到需要resverse的前一个节点
         for(int i=1;i<left;i++){
             pre = pre.next;
         }

         // 头插法，进行链表转置
         ListNode cur = pre.next;
         // 目标是把next插到pre后面
         ListNode nextNode;
         for(int i=0;i< right - left;i++){
              nextNode = cur.next;

              cur.next = nextNode.next;
              nextNode.next = pre.next;
              pre.next = nextNode;
              
         }

         return res.next;
    }
}

如何理解这段头插法算法：

nextNode = cur.next; // 等待插到pre后面的元素

cur.next = nextNode.next;  // 把nextNode摘出来(假设是C) 现在的情况是： A--B--D
nextNode.next = pre.next;  // 现在的情况是 AC同时指向B  A -- B --D
                           //                        C-- B
pre.next = nextNode;      // 最后一步 A--C；完成 A -- C -- B -- D

// 再下一个循环把D 插入A之后，就是  A--D--C--B ： BCD就完成了反转