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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @param head ListNode类 
 * @param m int整型 
 * @param n int整型 
 * @return ListNode类
 */
#include <stdio.h>
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
    if (!head || m == n) return head;

    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    struct ListNode* next = NULL;
    struct ListNode* head1 = NULL;  // m前的那个节点
    struct ListNode* tail1 = NULL;  // m位置的节点
    int count = 1;

    // 走到m位置
    while(count < m) {
        head1 = cur;
        cur = cur->next;
        count++;
    }
    tail1 = cur;   // 记住m节点（翻转后它会变成这一段的尾巴）

    // 翻转 m 到 n
    while(count <= n) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
        count++;
    }

    // 接回去
    if (head1) {
        head1->next = prev;   // m前的节点接到翻转后的头
    } else {
        head = prev;          // 如果m=1，新的头就是prev
    }
    tail1->next = cur;        // 原来的m节点变尾巴，接回后半部分

    return head;
}