每日一题：BM2 链表内指定区间反转

链表区间反转教学内容

1. 任务描述

给定一个链表和两个整数 m 和 n，你需要将链表从第 m 个节点到第 n 个节点之间的元素进行反转，返回反转后的链表。注意，链表的头节点也可能是反转区间的一部分，因此我们需要小心处理链表的连接。

2. 题目分析

• 输入: 一个链表和两个整数 m 和 n，表示要反转的区间。
• 输出: 返回反转后的链表。

例子

假设我们有以下链表 {1, 2, 3, 4, 5}，并且 m = 2，n = 4。

• 输入链表: {1, 2, 3, 4, 5}
• 反转区间: 从第 2 个节点到第 4 个节点，即 {2, 3, 4}
• 输出链表: {1, 4, 3, 2, 5}

3. 思路

为了实现链表区间反转，我们可以通过以下几个步骤：

1. 处理边界条件：如果链表为空或 m == n，不需要反转，直接返回原链表。
2. 引入虚拟头节点：为了方便处理链表头部，我们可以引入一个虚拟头节点。这样可以避免处理头节点特殊情况。
3. 定位反转区间：找到反转区间的前一个节点，这样我们可以方便地重新连接反转后的部分。
4. 反转区间内的节点：反转链表中指定区间的节点，直到达到 n - m 次。
5. 连接反转后的部分：反转完后，连接链表的前部分、反转后的部分以及链表的后部分。

4. 详细步骤

4.1 创建虚拟头节点

我们使用一个虚拟节点 dummy，它的 next 指向原链表的头节点。这有助于我们简化操作链表头部的复杂性。

4.2 寻找反转区间的前一个节点

我们通过遍历链表，使指针 start 指向反转区间前一个节点（即 m-1 位置的节点）。start 指针的作用是为了便于我们修改区间反转时的连接关系。

4.3 反转区间中的节点

接下来，我们利用一个 while 循环来反转区间中的节点。在每一步，我们将当前节点指向前一个节点，直到完成反转。

4.4 重新连接链表

反转结束后，我们需要确保反转区间前后的连接正确。start->next->next 要指向反转区间后面的节点，start->next 要指向反转区间的第一个节点。

4.5 返回结果

最终，返回 dummy->next，即新的链表头节点。

5. 代码实现

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param head ListNode类
 * @param m int整型
 * @param n int整型
 * @return ListNode类
 */
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {

   // 如果链表为空或者m和n相等，不需要反转
   if (head == NULL || m == n) 
        return head;

   // 创建一个虚拟节点，便于操作头节点
   struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
   dummy->next = head;
   
   // 让start指向反转区间前一个节点
   struct ListNode* start = dummy;
   for (int i = 1; i < m; i++) {
        start = start->next;
   }
   
   // pre指向反转区间的第一个节点
   struct ListNode* pre = start->next;
   struct ListNode* cur = pre->next;
   struct ListNode* next = cur ? cur->next : NULL;

   int temp = n - m;

   // 进行区间内的反转
   while (temp--) {
        cur->next = pre;
        pre = cur;
        cur = next;
        next = next ? next->next : NULL;
   }

   // 反转完成后，将起始位置的next节点和反转区间后的节点连接
   start->next->next = cur;
   start->next = pre;

   return dummy->next;  // 返回新的头结点
}

6. 代码解析

6.1 初始化虚拟头节点

struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
dummy->next = head;

通过创建一个虚拟头节点 dummy，我们避免了处理头节点的特殊情况。

6.2 寻找反转区间的前一个节点

struct ListNode* start = dummy;
for (int i = 1; i < m; i++) {
    start = start->next;
}

通过循环，我们让 start 指向反转区间的前一个节点。

6.3 反转区间中的节点

struct ListNode* pre = start->next;
struct ListNode* cur = pre->next;
struct ListNode* next = cur ? cur->next : NULL;

pre 指向反转区间的第一个节点，cur 指向第一个需要反转的节点，next 保存 cur 的下一个节点。

6.4 进行节点反转

int temp = n - m;
while (temp--) {
    cur->next = pre;
    pre = cur;
    cur = next;
    next = next ? next->next : NULL;
}

每次迭代时，将 cur 的 next 指针指向 pre，然后更新指针 pre、cur 和 next。

6.5 重新连接链表

start->next->next = cur;
start->next = pre;

完成反转后，重新连接链表的前部分和后部分。

6.6 返回新的链表

return dummy->next;

返回反转后的链表头节点。

7. 时间与空间复杂度分析

• 时间复杂度：$O(n)$，我们遍历了链表两次，第一次找到反转区间的前一个节点，第二次进行区间反转。
• 空间复杂度：$O(1)$，我们只使用了常数空间，所有操作都在原链表上进行。

通过以上内容，我们可以高效地完成链表区间反转问题的解决。