解答：

注意：题目中单链表带头结点，头结点不存储关键字。

思路一：开辟一个长度为 n 的辅助数组，将所有结点存入，然后直接操作数组下标，重新构建链表。该算法空间复杂度为 O(n) ，但是这里题目已经明确要求设计一个空间复杂度为 O(1) 的算法，所以不能使用。

所以本题只能使用一个原地算法。目前主流的解法如下：

寻找链表中点 + 反转链表 + 合并链表

目标链表即为将原链表的左半端和反转后的右半端合并后的结果。这样可以分为三步。

第一步：找到原链表的中点，本题为下中位数点  ，即第  个结点，为什么是找下中位数点，这道题将链表分成两段，左半段为  ，右半段为  ，这样能够满足当 n 为偶数时，左半段结点个数和右半段结点个数相等，当 n 为奇数时，左半段结点个数比右半段结点个数多 1。为什么要求当 n 为奇数时左半段结点个数比右半段结点个数多 1，因为第一个元素 a1 是左半段元素，这样交替后最后一个元素一定是左半段的元素，恰巧比右半段多出一个。

使用快慢指针可以方便找出链表中位于中位数位置的结点，该步时间复杂度 O(n) 。

第二步：将原链表的右半段反转。

反转链表有三种方法，递归法，迭代法，头插法。这三种方法中，迭代法是最优解。

这里使用迭代法实现链表的反转，该步时间复杂度 O(n) 。

第三步：将两条链表合并。

因为两链表长度相差不超过一，交叉合并，该步时间复杂度 O(n) 。

综上，该算法的时间复杂度为 O(n)+O(n)+O(n)=O(n) 。

C代码如下（含测试用例）：

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

typedef struct node {
    int data;
    struct node *next;
} NODE;

void reorderList(NODE* h) {
    NODE *p, *q, *r, *s;
    // 第一步：寻找h中间结点
    p = q = h;
    while (q->next != NULL) {
        p = p->next;
        q = q->next;
        if (q->next != NULL) {
            q = q->next;
        }
    }
    q = p->next;
    p->next = NULL;
    // 第二步：将链表后半段反转
    while (q != NULL) {
        r = q->next;
        q->next = p->next;
        p->next = q;
        q = r;
    }
    // 第三步：合并链表
    s = h->next;
    q = p->next;
    p->next = NULL;
    while (q != NULL) {
        r = q->next;
        q->next = s->next;
        s->next = q;
        s = q->next;
        q = r;
    }
}

NODE* createLinkedList(int *a, int n) {
    NODE* head = (NODE *)malloc(sizeof(struct node));
    NODE* tail = head;
    for (int i = 0; i < n; i++) {
        NODE* p = (NODE *)malloc(sizeof(struct node));
        p->data = a[i];
        p->next = NULL;
        tail->next = p;
        tail = tail->next;
    }
    return head;
}

int main() {
    int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    NODE* head = createLinkedList(a, 9);
    reorderList(head);
    NODE* curr = head;
    printf("head");
    while (curr != NULL) {
        printf("->%d", curr->data);
        curr = curr->next;
    }
    return 0;
}

说实话，标准答案的指针利用率非常高，缺点也很明显，可读性很差。

这道题实际上是三个基础算法的组合，本人把三段代码拆分三个方法。

C代码如下（含测试用例）：

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

typedef struct node {
    int data;
    struct node *next;
} NODE;

NODE* middleNode(NODE* head) {
    NODE* slow = head;
    NODE* fast = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

NODE* reverseList(NODE* head) {
    NODE* prev = NULL;
    NODE* curr = head;
    while (curr != NULL) {
        NODE* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

void mergeList(NODE* l1, NODE* l2) {
    NODE* l1_tmp;
    NODE* l2_tmp;
    while (l1 != NULL && l2 != NULL) {
        l1_tmp = l1->next;
        l2_tmp = l2->next;
        l1->next = l2;
        l1 = l1_tmp;
        l2->next = l1;
        l2 = l2_tmp;
    }
}

void reorderList(NODE* head) {
    if (head == NULL || head->next == NULL) {
        return;
    }
    NODE* mid = middleNode(head->next);
    NODE* l1 = head->next;
    NODE* l2 = mid->next;
    mid->next = NULL;
    l2 = reverseList(l2);
    mergeList(l1, l2);
}

NODE* createLinkedList(int *a, int n) {
    NODE* head = (NODE *)malloc(sizeof(struct node));
    NODE* tail = head;
    for (int i = 0; i < n; i++) {
        NODE* p = (NODE *)malloc(sizeof(struct node));
        p->data = a[i];
        p->next = NULL;
        tail->next = p;
        tail = tail->next;
    }
    return head;
}

int main() {
    int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    NODE* head = createLinkedList(a, 9);
    reorderList(head);
    NODE* curr = head;
    printf("head");
    while (curr != NULL) {
        printf("->%d", curr->data);
        curr = curr->next;
    }
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
using namespace std;

typedef struct node {
    int data;
    struct node *next;
} NODE;

NODE* middleNode(NODE* head) {
    NODE* slow = head;
    NODE* fast = head;
    while (fast->next != nullptr && fast->next->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

NODE* reverseList(NODE* head) {
    NODE* prev = nullptr;
    NODE* curr = head;
    while (curr != nullptr) {
        NODE* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

void mergeList(NODE* l1, NODE* l2) {
    NODE* l1_tmp;
    NODE* l2_tmp;
    while (l1 != nullptr && l2 != nullptr) {
        l1_tmp = l1->next;
        l2_tmp = l2->next;
        l1->next = l2;
        l1 = l1_tmp;
        l2->next = l1;
        l2 = l2_tmp;
    }
}

void reorderList(NODE* head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }
    NODE* mid = middleNode(head->next);
    NODE* l1 = head->next;
    NODE* l2 = mid->next;
    mid->next = nullptr;
    l2 = reverseList(l2);
    mergeList(l1, l2);
}

NODE* createLinkedList(int *a, int n) {
    NODE* head = new NODE();
    NODE* tail = head;
    for (int i = 0; i < n; i++) {
        NODE* p = new NODE();
        p->data = a[i];
        p->next = nullptr;
        tail->next = p;
        tail = tail->next;
    }
    return head;
}

int main() {
    int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    NODE* head = createLinkedList(a, 9);
    reorderList(head);
    NODE* curr = head;
    cout << "head";
    while (curr != nullptr) {
        cout << "->"<< curr->data;
        curr = curr->next;
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(n) 。
• 空间复杂度： O(1) 。