问题描述
LeetCode 92. 反转链表 II (opens in a new tab)，难度中等。
给你单链表的头指针 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
进阶： 你可以使用一趟扫描完成反转吗？
题解
链表
解题思路：根据 left，right 下标，我们可以将整个链表拆分成三部分，以示例 1 为例，left = 2， right = 4
1 → 2 → 3 → 4 → 5
first: 1
second: 2 → 3 → 4
third: 5我们只需要将 second 部分的链表反转（参考 206. 反转链表 (opens in a new tab)），然后按照 first → second → third 重新连接链表即可。但有几个注意点：
left == rightleft == 1right == ListLength（链表最后一个节点的下标）
Solution.java
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
// 如果只反转一个节点，直接返回
if (left == right || head == null) return head;
int leftIndex = left - 1;
int len = right - left + 1;
ListNode first = null;
ListNode second;
ListNode third = null;
// 第一段（判断第二段是否是从下标为 1 开始）
if (left > 1) {
first = head;
while (--leftIndex > 0) {
first = first.next; // 找到 left 的前驱节点
}
}
// 第二段
if (first != null) {
second = first.next;
first.next = null; // 第一段结尾以 null 封尾
} else {
second = head;
}
ListNode temp = second;
while (--len > 0 && temp != null) {
temp = temp.next;
}
// 第三段
if (temp != null) {
third = temp.next; // 找到 right 节点
temp.next = null; // 第二段结尾以 null 封尾
}
// 第二段链表反转后重新拼接
List<ListNode> a = reverseList(second);
if (first != null) {
first.next = a.get(1);
} else {
head = a.get(1);
}
a.get(0).next = third;
return head;
}
// 参考 https://leetcode.cn/problems/reverse-linked-list/
public List<ListNode> reverseList(ListNode head) {
if (head == null) return null;
List<ListNode> result = new ArrayList<>();
result.add(head);
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
result.add(prev);
return result;
}
}