云职上海企业服务有限公司_在线代理app_青岛网站建设公司电话_seo代理计费系统

题目描述

92. 反转链表 II

给你单链表的头指针 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 <= 500
• 1 <= left <= right <= n

分析解答

这道题和反转链表的唯一不同是它存在起始和结束位置，所以我们只需要在原有反转链表的基础上，再思考一下如何将反转后的小链表和之前的链表连接起来，也就是需要多思考两个指针（next）的指向。

代码如下：

/*** Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? null : next)* }*/
function ListNode(val, next) {this.val = (val===undefined ? 0 : val)this.next = (next===undefined ? null : next)
}
/*** @param {ListNode} head* @param {number} left* @param {number} right* @return {ListNode}*/
var reverseBetween = function(head, left, right) {if (!head || left === right) return head;let dummy = new ListNode(0); // 创建虚拟头节点dummy.next = head;let prev = dummy;for (let i = 0; i < left - 1; i++) {prev = prev.next;}let current = prev.next;for (let i = 0; i < right - left; i++) {let next = current.next;current.next = next.next;next.next = prev.next;prev.next = next;}return dummy.next;
};

重点在于：

let next = current.next;
current.next = next.next;
next.next = prev.next;
prev.next = next;

对比普通反转列表代码：

let temp = cur.next; 
cur.next = pre; 
pre = cur; 
cur = temp;

普通反转链表（全部反转）：

1. 缓存下一个值
2. 改变 cur 的 next 指向（指向上一个）
3. pre 移动到 cur 的位置
4. cur 移动到下一个位置（缓存值）

部分反转：

1. 缓存下一个值
2. 改变 cur 的 next 指向（指向下一个的下一个）
3. 改变下一个值的 next 指向
4. 改变上一个值的 next 指向

除此之外，如果需要反转三个数据。部分反转循环代码块执行两次（反转两次）；而全部反转循环代码块执行三次（反转三次，有一次 null 头节点）。

这样看来，只是三四代码语句有区别，而这两句代码正好对应了我上面说到的那两次不同的指针改变。

思路拓展