反转链表 II
- 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
解题思路1
1、遍历链表:
- 找到 left 前面的节点（preLeft），以及 left 节点本身（leftNode）。
- 找到 right 节点（rightNode），以及 right 后面的节点（postRight）。
2、反转部分链表: - 将 leftNode 到 rightNode 之间的节点进行反转。
3、重新连接: - 将 preLeft 的 next 指向 rightNode。
- 将 leftNode 的 next 指向 postRight。
java实现1
public class ReverseBetween {
public static class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public ListNode reverseBetween(ListNode head, int left, int right) {
// 创建虚拟头节点，简化边界处理
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
ListNode preLeft = dummyNode;
// 第 1 步：找到 left 节点的前一个节点 pre
for (int i = 0; i < left - 1; i++) {
preLeft = preLeft.next;
}
// 第 2 步：找到 right 节点
ListNode rightNode = preLeft;
for (int i = 0; i < right - left + 1; i++) {
rightNode = rightNode.next;
}
// 第 3 步：切断出一个子链表（截取链表）
ListNode leftNode = preLeft.next;
ListNode postRight = rightNode.next;
// 切断链接
preLeft.next = null;
rightNode.next = null;
// 第 4 步：反转链表的子区间
reverseLinkedList(leftNode);
// 第 5 步：接回到原来的链表中
preLeft.next = rightNode;
leftNode.next = postRight;
return dummyNode.next;
}
private void reverseLinkedList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
}
public static void main(String[] args) {
ReverseBetween reverseBetween = new ReverseBetween();
// 创建示例链表 1->2->3->4->5
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
// 测试反转第2到第4个节点
ListNode newHead = reverseBetween.reverseBetween(head, 2, 4);
printList(newHead); // 输出: 1->4->3->2->5
}
// 辅助方法：打印链表
public static void printList(ListNode head) {
ListNode current = head;
while (current != null) {
System.out.print(current.val);
if (current.next != null) {
System.out.print("->");
}
current = current.next;
}
System.out.println();
}
}
时间空间复杂度1
-
时间复杂度：O(N)，其中 N是链表总节点数。最坏情况下，需要遍历整个链表。
-
空间复杂度：O(1)。只使用到常数个变量。
解题思路2
解题思路1缺点是：如果 left 和 right 的区域很大，恰好是链表的头节点和尾节点时，找到 left 和 right 需要遍历一次，反转它们之间的链表还需要遍历一次，虽然总的时间复杂度为 O(N)，但遍历了链表 2 次。
1、初始化和定位：
- 使用指针 pre 遍历到 left 前一个节点，定位到反转区间的前一个节点。
局部反转：
2、使用三个指针 pre、cur 和 next 进行反转操作：
-
pre 指向反转区间的前一个节点。
-
cur 指向当前需要反转的节点。
-
next 指向当前节点的下一个节点，用于在反转过程中进行位置交换。
3、反转区间： -
通过逐个移动 cur 和 next 节点的位置，在反转区间内执行交换操作，完成局部反转。
图解：
核心代码分析：
// 先将 curr 的下一个节点记录为 next；
next = cur.next;
//执行操作1：把 curr 的下一个节点指向 next 的下一个节点
cur.next = next.next;
//执行操作2：把 next 的下一个节点指向 pre 的下一个节点
next.next = pre.next;
//执行操作3：把 pre 的下一个节点指向 next
pre.next = next;
后续同理
java实现2
public class ReverseBetween {
public static class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public ListNode reverseBetween(ListNode head, int left, int right) {
// 设置 dummyNode 是这一类问题的一般做法
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
ListNode pre = dummyNode;
//找到pre结点
for (int i = 0; i < left - 1; i++) {
pre = pre.next;
}
//当前current节点
ListNode cur = pre.next;
ListNode next;
for (int i = 0; i < right - left; i++) {
// cur的下一个节点赋值给next
next = cur.next;
//cur指向next指向的节点
cur.next = next.next;
//next指向pre指向的节点
next.next = pre.next;
//pre指向next
pre.next = next;
}
return dummyNode.next;
}
public static void main(String[] args) {
ReverseBetween reverseBetween = new ReverseBetween();
// 创建示例链表 1->2->3->4->5
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
// 测试反转第2到第4个节点
ListNode newHead = reverseBetween.reverseBetween(head, 2, 4);
printList(newHead); // 输出: 1->4->3->2->5
}
// 辅助方法：打印链表
public static void printList(ListNode head) {
ListNode current = head;
while (current != null) {
System.out.print(current.val);
if (current.next != null) {
System.out.print("->");
}
current = current.next;
}
System.out.println();
}
}
时间空间复杂度2
-
时间复杂度：O(N)，其中 N 是链表总节点数。最多只遍历了链表一次，就完成了反转。
-
空间复杂度：O(1)。只使用到常数个变量。