题解 | #链表内指定区间反转#

/**
 * 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) {
    int i;
    struct ListNode **indirect = &head, *eop;
    struct ListNode *current, *temp;
 
    for (i = 0; i < m - 1; i++)
        indirect = &(*indirect)->next;

    if (*indirect) {
        eop = *indirect;
        current = eop->next;
        for (i = m; i < n; i++) {
            temp = current->next;
            current->next = *indirect;
            *indirect = current;
            current = temp;
        }
        eop->next = current;
    }
    return head;
}

提交之后看了几个榜上比较通用的题解，应该不会有比我更优的C语言版本了：

1. 不需要用malloc，减少额外的申请释放开销，
2. 不需要多余的指针变量，极度压缩栈帧空间，

这题的核心难点是如何处理边界条件，当m=1时，如果是普通解法，就会使用到malloc和多余的栈指针，同时增加if的分支，其实没有必要，灵感来自于linux kernel对于链表遍历的实现，利用间访可以有效把m=1的边界case和其他普通case结合起来。