C 语言初阶数据结构习题（二）

🎄一、链表内指定区间翻转

题目描述：链表内指定区间翻转

解题思路：

1. 首先处理特殊情况，如果 m == n 时，说明反转的区间只有一个节点，无需进行任何操作，直接返回原链表的头节点 head。
2. 创建一个虚拟头节点 ret，并将其 next 指针指向链表的头节点 head。（虚拟头节点的作用是简化边界情况的处理，例如当反转区间包括头节点时，可以避免复杂的头插操作。）
3. 使用两个指针 pm 和 pn。pn 用于定位反转区间的前一个节点，pm 用于定位反转区间的起始节点。
4. 通过第一个 for 循环，可以将 pm 指向第 m 个节点，pn 指向第 m - 1 个节点。
5. 再通过使用第二个 for 循环，从第 m 个节点开始，逐个反转节点，直到第 n 个节点。
6. 最后返回虚拟头结点的下一个节点即（ret -> next）即反转后的链表的头节点。

代码实现：

struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
    struct ListNode* ret = (struct ListNode*)malloc(sizeof(struct ListNode));
    ret->next = head;
    struct ListNode* pm = ret;
    struct ListNode* pn = head;
    if (m == n) {
        return head;
    }
    for (int i = ; i < m; i++) {
        pn = pm;
        pm = pm->next;
    }
     ( i = m; i < n; i++) {
         pm->next;
        pm->next = mid->next;
        mid->next = pn->next;
        pn->next = mid;
    }
     ret->next;
}