1. 题目描述

problem link

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

2. 解题

要求翻转m到n之间的元素，顺着题的思路想，先找到第m个元素，然后用头删头插法翻转到第n个元素，最后把头到m、m到n、n到尾这三部分拼接起来就ok了。

思路听起来很简单，但我越写越乱，差点还把自己绕进去了。。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
    if (head == NULL || head->next == NULL) {
        return head;
    }

    struct ListNode *start = NULL, *end = NULL;  // start指向m前一个元素 end指向n后一个元素，方便拼接
    struct ListNode *dummyHead = 
        (struct ListNode *)malloc(sizeof(struct ListNode));
    dummyHead->next = head;
    dummyHead->val = 0;
    struct ListNode *ptr = dummyHead;
    struct ListNode *res = NULL, *curr = NULL;  // 用于翻转元素
    int count = 0;

    while (count + 1 != m) {  // ptr先找到m前一个元素
        ptr = ptr->next;
        count++;
    }

    start = ptr;
    ptr = ptr->next;  
    count++;

    while (count <= n) {  // 翻转m到n之间的元素
        curr = ptr;
        ptr = ptr->next;
        count++;

        curr->next = res;
        res = curr;
    }

    end = ptr;
    start->next = res;

    ptr = res;
    while (ptr->next) {
        ptr = ptr->next;
    }
    ptr->next = end;

    return dummyHead->next;

}

struct ListNode* CreatLL(int* arr, int size) {
    struct ListNode* dummyHead =
        (struct ListNode *)malloc(sizeof(struct ListNode));
    dummyHead->val = 0;
    dummyHead->next = NULL;
    struct ListNode* ptr = dummyHead;
    struct ListNode* tmp;

    for (int i = 0; i < size; i++) {
        tmp = (struct ListNode *)malloc(sizeof(struct ListNode));
        tmp->next = NULL;
        tmp->val = arr[i];
        ptr->next = tmp;
        ptr = ptr->next;
    }

    return dummyHead->next;
}

void printLL(struct ListNode* head) {
    struct ListNode* ptr = head;
    while (ptr) {
        printf("%d -> ", ptr->val);
        ptr = ptr->next;
    }
    putchar('\n');
}

int main() {
    int arr[] = { 1, 4, 3, 2, 5, 2 };
    struct ListNode* head = CreatLL(arr, 6);
    printLL(head);
    head = reverseBetween(head, 1, 1);
    printLL(head);

    system("pause");
    return 0;
}