c语言链表内指定区间反转

1.问题描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 ，空间复杂度 。
例如：
给出的链表为
返回

数据范围： 链表长度 ，，链表中每个节点的值满足
要求：时间复杂度 ，空间复杂度
进阶：时间复杂度 ，空间复杂度

2.源码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

typedef struct ListNode ListNode;

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

void ListPush(ListNode **head, int val)
{
    ListNode *pre = NULL;
    ListNode *cur = (*head);

    if(cur == NULL)
    {
        *head = (ListNode *)malloc(sizeof(ListNode));

        (*head)->val = val;
        (*head)->next = NULL;

        return;
    }

    while(cur)
    {
        pre = cur;
        cur = cur->next;
    }

    cur = (ListNode *)malloc(sizeof(ListNode));

    pre->next = cur;
    cur->val = val;
    cur->next = NULL;

    return;
}

void ListFree(ListNode **head)
{
    ListNode *next = NULL;
    ListNode *cur = (*head);

    while(cur)
    {
        next = cur->next;

        free(cur);

        cur = next;
    }

    *head = NULL;
}

void ListPrint(ListNode *head)
{
    ListNode *cur = head;

    while(cur)
    {
        printf("%d ", cur->val);

        cur = cur->next;
    }

    printf("\n");
}

struct ListNode *reverseBetween(struct ListNode *head, int m, int n)
{
    struct ListNode *pre = NULL;
    struct ListNode *cur = head;
    struct ListNode *next = NULL;
    struct ListNode *left = NULL;
    int i;

    if(head)
    {
        next = cur->next;
    }

    if(m == 1)
    {
        left = cur;

        for(i=0; i<n; i++)
        {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }

        head = pre;

        left->next = next;

        return head;
    }

    for(i=0; i<m-1; i++)
    {
        pre = cur;
        cur = cur->next;
        next = cur->next;
    }

    left = cur;

    for(i=m-1; i<n-1; i++)
    {
        next = cur->next;
        cur->next = next->next;
        next->next = pre->next;
        pre->next = next;
    }

    return head;
}

int main()
{
    ListNode *head = NULL;

    ListPush(&head, 5);
    ListPush(&head, 2);
    ListPush(&head, 3);
    /*ListPush(&head, 4);
    ListPush(&head, 5);*/

    ListPrint(head);

    head = reverseBetween(head, 1, 2);

    ListPrint(head);

    ListFree(&head);

    return 0;
}

3.编译源码

$ gcc -o test  test.c -std=c89

4.运行及其结果

$ ./test
5 2 3 
2 5 3