反转链表 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 节点的前一个节点 prefor (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->5ListNode 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：指向待反转区域的第一个节点 left；
- next：永远指向 curr 的下一个节点，循环过程中，curr 变化以后 next 会变化；
- pre：永远指向待反转区域的第一个节点 left 的前一个节点，在循环过程中不变。
// 先将 curr 的下一个节点记录为 next；next = cur.next;//执行操作1：把 curr 的下一个节点指向 next 的下一个节点cur.next = next.next;//执行操作2：把 next 的下一个节点指向 pre 的下一个节点next.next = pre.next;//执行操作3：把 pre 的下一个节点指向 nextpre.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的下一个节点赋值给nextnext = cur.next;//cur指向next指向的节点cur.next = next.next;//next指向pre指向的节点next.next = pre.next;//pre指向nextpre.next = next;}return dummyNode.next;}public static void main(String[] args) {ReverseBetween reverseBetween = new ReverseBetween();// 创建示例链表 1->2->3->4->5ListNode 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)。只使用到常数个变量。