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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param m int整型 
 * @param n int整型 
 * @return ListNode类
 */
#include <stdlib.h>
/*法一： （虚拟头 + 头插法）反转链表 + 查询反转的前一个节点 + 终点结束 */
struct ListNode* reverseBetween(struct ListNode* head, int m, int n )
{
    if(m == n | head ==NULL)return head;
    //虚拟头：处理从头开始反转的情况
    struct ListNode* virtual_head = malloc(sizeof(struct ListNode));
    virtual_head->next = head;
    virtual_head->val =-1;

    //查询起点前一个节点
    struct ListNode* start=virtual_head;
    int num=1;
    //后移m-1次到反转前一个
    while (num < m) {
        start = start->next;
        num++;
    }

    //查询反转的尾节点、以及工作节点（要动的节点）
    struct ListNode* tail=start->next;
    struct ListNode* work=tail->next;

    for(int i=0;i<n-m;i++){
        //注意tail本身是不动的，主要把work头插到start后
        tail->next = work->next;
        work->next = start->next;
        start->next = work;
        //工作指针置位
        work = tail->next;
    }
    return virtual_head->next;
}