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

/**
 * 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 ) {
    // write code here
    struct ListNode *pre = head;
    struct ListNode *cur = head;
    struct ListNode *next = head;
    struct ListNode *preTrt = head;
    struct ListNode *trt = head;

    if (head == NULL) {
        return head;
    }

    /*  查找反转位置 */
    for (int i = 1; i < m; i++) {
        if (i == m) {
            break;
        }
        /* 记录反转节点的前一个节点，用于反转后链接 */
        preTrt = cur;
        cur = cur->next;
    }

    pre = cur;
    cur = cur->next;
    /* 记录反转的开始位置，反转后成为反转区间的最后一个节点，用于连接后面节点 */
    trt = pre;

    /* 对反转区间节点进行反转 */
    while (m < n) {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
        m++;
    }

    /* 反转后链接后面节点 */
    trt->next = cur;

    /* 用反转区间的前一个节点连接反转区间
       1、若反转区间前一个节点是head节点，则无需连接，直接返回反转区间
       2、若反转区间前一个节点非head节点，则需要连接，连接后返回head
    */
    if (preTrt == trt) {
        return pre;
    } else {
        preTrt->next = pre;
        return head;
    }
}