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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param m int整型 
 * @param n int整型 
 * @return ListNode类
 */
struct ListNode* ReverseList_two(struct ListNode* head, int a, int b ) 
{    
    if (a == b)
        return head;
    
    // write code here
    int i =1;
    struct ListNode *r = head;
    
    struct ListNode *s = NULL;
    struct ListNode *z = head;
    
    struct ListNode *sa = NULL;
    struct ListNode *za = NULL;
    struct ListNode *xa = NULL;
    
    struct ListNode *sb = NULL;
    struct ListNode *zb = NULL;
    struct ListNode *xb = NULL;
    
    while(z) // 遍历完整个链表
    {
        if (i == a) // 记录 a 处的 上一个 这一个 下一个
        {
            sa = s;
            za = z;
            xa = z->next;
        }
        else if (i == b) // 记录 a 处的 上一个 这一个 下一个
        {
            sb = s;
            zb = z;
            xb = z->next;
            
            if(a == 1) // 如果交换的是第一个,修改储存的返回值
                r = zb;
            break;
        }
        s = z;
        z = z->next;
        i++;
    }
    
    if (sa) // a 是第一个,没有上一个,跳过
    sa->next = zb; // a 的上一个的下一个改成 b 的这一个
    if (sb != za) // b 的上一个的下一个和 a 的这一个相同,表示 ab 连续
    sb->next = za; // b 的上一个的下一个改成 a 的这一个
    zb->next = zb != xa ? xa : za; // b 的下一个 改成 a 的下一个, 如果 a 的下一个就是 b ,表示 ab 连续, b 的下一个就是 a
    za->next = xb; // a 的下一个 改成 b 的下一个
    
    return r; // 返回链表头
}


struct ListNode* ReverseList(struct ListNode* head, int n1, int n2) 
{
    if (n1 == n2 || head == NULL || head->next == NULL)
        return head;
    
    struct ListNode* h = head;
    struct ListNode* a = NULL; // n1 -1
    struct ListNode* b = head; // n2 + 1
    struct ListNode* c = head->next; // n1
    
    int n=1;
    
    while(1)
    {
        if (n == n1-1) 
            a = b;
        if (n == n2) 
            break;
        b = c;
        c = c->next;
        n++;
    }
    b = c;
    c = a ? a->next : head;
    
    struct ListNode* s = a; 
    struct ListNode* z = c; 
    struct ListNode* x = z->next;
    
    n = 0;
    while(n++ <= n2 - n1)
    {
        x = z->next;
        z->next = s;
        s = z;
        z = x;
    }
    
    c->next = b;
    if (a)
        a->next = s;
    else
        head = s;
    
    return head; // 返回 上一个    
}

// 主函数调用 在2种方法之间切换
struct ListNode* reverseBetween(struct ListNode* head, int a, int b ) 
{    
    if (1)
    {
        return ReverseList(head, a, b); // 一个区间内整体反序
    }
    else
    {
        for (int i=0; i<=(b-a)/2; i++)
        {
            head = ReverseList_two(head, a+i, b-i); // 单独调换2个节点
        }
        return head;
    }
}