#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

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