void change_list(NODE *h)
{
    NODE *p,*q,*r,*s;
    p=q=h;
    
    while(q->next!=NULL)//寻找中间结点
    {
        p=p->next;//p走一步
        q=q->next;
        if(q->next!=NULL)
            q=q->next; //q走两步
    }
    q=p->next;//p所指结点为中间结点，q为后半段链表的首结点
    p->next=NULL;
    while (q!=NULL)//将链表后半段逆置
    {
            r=q->next;
            q->next=p->next;
            p->next=q;
            q=r;
    }
        
    s=h->next;//s指向前半段的第一个数据结点，即插入点
    q=p->next;//q指向后半段的第一个数据结点
    p->next=NULL;
    while(q!=NULL)//将链表后半段的结点插入到指定位置
    { 
        r=q->next;//r指向后半段的下一个结点
        q->next=s->next; //将q所指结点插入到s所指结点之后
        S->next=q;
        S=q->next;//s指向前半段的下一个插入点
        q=r;
    }
}

#include<stdio.h>
#include<malloc.h>
typedef struct node {
    struct node* next;
    int data;
}node;
node* initlinklist(int a[], int size) {
    node* p = (node*)malloc(sizeof(node));
    p->data = a[0];
    p->next = NULL;
    node* temp = p;
    for (int i = 1; i < size; i++) {
        node* b = (node*)malloc(sizeof(node));
        b->data = a[i];
        b->next = NULL;
        temp->next = b;
        temp = temp->next;
    }
    return p;
}
void printlist(node* p) {
    node* temp = p;
    while (temp != NULL) {
        printf("%d", temp->data);
        if (temp->next != NULL)
            printf("->");
        temp = temp->next;
    }
    putchar(10);
}
//找到中间节点
node* findmiddle(node* head) {
    node* slow = head, * fast = head;
    while (fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow; 
}
//反转链表
node* reversive(node* head) {
    node* newhead = NULL,*temp=NULL;
    if (head==NULL||head->next==NULL)
        return head;
    while(head!=NULL){
        temp = head;
        head = head->next;
        temp->next = newhead;
        newhead = temp;
    }
    return newhead;
}
//重新链接链表
void recover(node* head) {
    if (!head || !head->next)
        return;
    node* middle = findmiddle(head);
    node* secondhalf = middle->next;
    middle->next = NULL;//切断

    secondhalf = reversive(secondhalf);//翻转后半段

    node* firsthalf = head;
    while (secondhalf) {
        node* temp1 = firsthalf->next;
        node* temp2 = secondhalf->next;

        firsthalf->next = secondhalf;
        secondhalf->next = temp1;

        firsthalf = temp1;
        secondhalf = temp2;
    }
}
int main()
{
    int a[] = { 1,2,3,4,5,6,7,8,9 };
    int size = sizeof(a) / sizeof(a[0]);
    node* head = initlinklist(a, size);
    printlist(head);
    recover(head);
    printlist(head);
    return 0;
} 

findmiddleO(n)

reversiveO(n)

recoverO(n)

总复杂度O(n)

1

https://rainbow452.notion.site/P1496-85038b5808d2403cbd356ba83562c185?pvs=4

逆置后半段链表，两个指针就能实现