力扣92题：反转链表 II

力扣92题：反转链表 II

题目描述

给你单链表的头指针 head 和两个整数 left 和 right，其中 $1\le left\le right\le$ 链表长度。请你反转从位置 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]

---

解题思路

1. 分段处理链表：
   将链表分为三部分：

   • pre 部分：从头节点到 left - 1 的节点；
   • reverse 部分：从 left 到 right 的节点；
   • post 部分：从 right + 1 到链表末尾的节点。

2. 反转链表的中间部分：
   使用原地反转法，将 reverse 部分的节点顺序反转。

3. 重新连接链表：
   通过调整指针，将三部分重新连接为一个完整的链表。

---

C语言实现

以下是基于上述思路的代码实现：

#include <stdio.h>
#include <stdlib.h>// 定义链表节点结构体
struct ListNode {int val;struct ListNode *next;
};// 反转链表 II 主函数
struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {if (head == NULL || left == right) return head;struct ListNode dummy; // 哨兵节点dummy.next = head;struct ListNode *prev = &dummy;// 1. 找到 left 节点的前驱for (int i = 1; i < left; i++) {prev = prev->next;}// 2. 反转链表的 [left, right] 部分struct ListNode *curr = prev->next;struct ListNode *next = NULL;for (int i = 0; i < right - left; i++) {next = curr->next;curr->next = next->next;next->next = prev->next;prev->next = next;}// 3. 返回新的链表头return dummy.next;
}// 辅助函数：创建链表
struct ListNode* createList(int* arr, int size) {struct ListNode *head = NULL, *tail = NULL;for (int i = 0; i < size; i++) {struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));node->val = arr[i];node->next = NULL;if (head == NULL) {head = tail = node;} else {tail->next = node;tail = node;}}return head;
}// 辅助函数：打印链表
void printList(struct ListNode* head) {while (head) {printf("%d -> ", head->val);head = head->next;}printf("NULL\n");
}// 主函数测试
int main() {int arr[] = {1, 2, 3, 4, 5};struct ListNode* head = createList(arr, 5);printf("原链表: ");printList(head);head = reverseBetween(head, 2, 4);printf("反转后链表: ");printList(head);return 0;
}

---

测试用例

示例 1

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2

输入：head = [5], left = 1, right = 1
输出：[5]

---

代码解析

1. 定义哨兵节点

struct ListNode dummy;
dummy.next = head;

通过哨兵节点简化对头节点的处理逻辑，避免头节点变化时单独处理。

2. 找到 left 的前驱节点

for (int i = 1; i < left; i++) {prev = prev->next;
}

prev 最终指向 left 节点的前驱。

3. 反转 [left, right] 区间的链表

struct ListNode *curr = prev->next;
for (int i = 0; i < right - left; i++) {next = curr->next;curr->next = next->next;next->next = prev->next;prev->next = next;
}

采用头插法逐步反转链表，核心逻辑如下：

• curr 表示当前节点；
• next 表示当前节点的下一个节点；
• 将 next 插入到 prev 之后，实现反转。

---

复杂度分析

1. 时间复杂度：
   遍历链表一次，复杂度为 $O(n)$。

2. 空间复杂度：
   只使用常数级额外空间，复杂度为 $O(1)$。