网络异常，图片无法展示
|
「这是我参与11月更文挑战的第22天，活动详情查看：2021最后一次更文挑战」
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：
网络异常，图片无法展示
|
输入： head = [1,2,3,4,5], left = 2, right = 4 输出： [1,4,3,2,5] 复制代码
示例 2：
输入： head = [5], left = 1, right = 1 输出： [5] 复制代码
提示：
- 链表中节点数目为
n 1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n
进阶： 你可以使用一趟扫描完成反转吗？
本题其实就是查找指定节点与反转链表的结合而已
主体思路即：首先找到待反转区间，将待反转区间反转，然后再接回原链表即可
详细解题思路如下：
- 特判：如果 left===right 则不需要反转，直接返回原链表即可
- 创建虚拟头节点
vhead,vhead.next = head,虚拟头可以方便我们后续的操作（举例：如果待反转区间包含头节点，则返回值特殊判断，有了虚拟头只要返回vhead.next即可） - 定义三个指针
pre = vhead、start = head、end = head - 根据
left、right的值向后调整pre、start、end的位置为待反转区间的前一个节点，待反转区间的开始位置和结束位置 - 通过
end.next获取待反转区间的下一个节点nextHead - 编写
reverse函数反转待反转区间并返回反转后链表的头尾节点（对链表反转不熟悉的小伙伴可以看我之前这篇文章 《反转链表》） - 通过之前记录的
pre指针连接反转后链表的头节点，通过nextHead连接返回链表的尾节点 - 最后返回
vhead.next即可
完整过程如下：
网络异常，图片无法展示
|
代码如下：
// 反转链表 function reverse(start,end){ let pre = start, next = start.next; // 从后向前的反转next指针 while(next!==end){ const next_next = next.next; next.next = pre; pre = next; next = next_next; } next.next = pre; return [end,start] } var reverseBetween = function(head, left, right) { // 如果 left===right 则不需要反转 if(left === right) return head; // 创建虚拟头节点 const vhead = new ListNode(0); vhead.next = head; // 待反转区间的前一个节点 let pre = vhead, // 待反转区间的头尾节点 start = end = head; // 找到待反转区间 while(right>1){ left--,right--; if(left>0){ pre = pre.next; start = start.next; } end = end.next; } // 待反转区间的下一个节点 const nextHead = end.next; // 反转待反转区间 [start,end] = reverse(start,end); // 将反转后的链表区间链接到原链表中 pre.next = start; end.next = nextHead; return vhead.next; }; 复制代码
至此我们就完成了 leetcode-92-反转链表 II
如有任何问题或建议，欢迎留言讨论！
