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

/**
 * 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 ) {
    // write code here
    struct ListNode *Node_P1 = head;

    //求出链表长度
    int len = 0;
    while (Node_P1) 
    {
        len++;
        Node_P1 = Node_P1->next;
    }

    //申请数组保存链表数据
    int arr_len = n-m+1;
    int *result = (int*)malloc(sizeof(int) * arr_len);

    Node_P1 = head;
    int i;
    for(i=1;i<m;i++)
    { 
        Node_P1 = Node_P1->next;
    }

    //利用数组保存区间数据
    for(i=0;i<arr_len;i++)
    {
        result[i] = Node_P1->val;
        Node_P1 = Node_P1->next;
    }


    //再利用数组，反转数据
    int *p1 = result;
    int *p2 = &result[arr_len-1];
    for(i=0;i<arr_len/2;i++)
    {
        *p1 = *p1 + *p2;
        *p2 = *p1 - *p2;
        *p1 = *p1 - *p2;
        p1++;
        p2--;
    }
    
    //将反转的数组，赋值到对应的链表区间
    Node_P1 = head;//指针归位
    for(i=1;i<m;i++)
    {
        Node_P1 = Node_P1->next;//移动到区间的前面
    }

    for(i=0;i<arr_len;i++)
    {
        Node_P1->val = result[i]; 
        Node_P1 = Node_P1->next;
    }
    
    free(result);

    return head;


}

核心思路：将要反转的区间数据，放入数组中，对数组进行反转后，赋值给区间链表。

步骤

1.求出区间长度，动态申请数组存储数据。

2.将指针移动需要反转的区间前，把这段区间数据存入数组。

3.利用数组进行反转。

4.将反转后的数组数据赋值到对应的链表区间。