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

/**
 * 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)
        return head;
    struct ListNode *newHead, *priorNode, *curr, *curr_next;
    newHead = (struct ListNode*) malloc(sizeof(struct ListNode)); //创建虚拟头结点，让m =0时的操作和m非零时保持一致
    newHead->next = head;

    //寻找区间左端点
    int i = 0;
    struct ListNode *p = newHead;
    while (i < m - 1) {
        p = p->next;
        i++;
    }
    priorNode = p;
    curr = priorNode->next;
    for (i = 0; i < n - m; i++) {
        curr_next = curr->next;
        curr->next = curr_next->next;
        curr_next->next = priorNode->next;
        priorNode->next = curr_next;
    }

    return newHead->next;
}

思路：

1、为保持m=0和m非零时的操作一致，为链表添加一个头结点

2、首先遍历链表找到区间左端点的前一个结点，保存在priorNode中，区间左端点结点保存在curr中。（在逆置过程中两指针所指结点保持不变），curr_next为curr的后继结点，在逆置过程中指向要操作的结点

3、从区间左端点开始，使用头插法，每次将curr_next所指的结点插入到priorNode后面，共执行 n - m次（区间内共n-m+1个结点，只需将后 n-m个依次放到最前面即可，每次循环完成一次头插，共n-m次）

第一次循环：curr_next 指向数据为3的结点，将其插入到prior后面

第二次循环：curr_next指向数据为4的结点，将其插入到prior后面

第三次循环即可完成指定区间结点的逆置