将给定的单链表L：L0→L1→L2→…→Ln-2→Ln-1→Ln​ 重新排序为：L0→Ln→L1→Ln-1→L2→Ln-2→… 要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。 数据范围：链表长度 0≤n≤20000 ，链表中每个节点的值满足 0≤val≤1000。 示例1 输入：{1,2,3,4} 返回值：{1,4,2,3} 说明：给定head链表1->2->3->4, 重新排列为 1->4->2->3,会取head链表里面的值打印输出 示例2 输入：{1,2,3,4,5} 返回值：{1,5,2,4,3} 说明：给定head链表1->2->3->4->5, 重新排列为 1->5>2->4->3,会取head链表里面的值打印输出，使用C语言实现

好的，以下是C语言实现的代码。

首先定义链表的节点结构体。

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

然后实现链表反转的函数。

struct ListNode* reverse(struct ListNode* head) {
    struct ListNode *pre = NULL, *cur = head, *nxt;
    while (cur) {
        nxt = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nxt;
    }
    return pre;
}

接下来实现链表重排的函数。

void reorderList(struct ListNode* head) {
    if (!head || !head->next) {
        return;
    }
    
    // 使用快慢指针找出链表的中点
    struct ListNode *slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // 将后半部分链表反转
    struct ListNode *p = slow->next;
    slow->next = NULL;
    p = reverse(p);
    
    // 将前半部分链表和反转后的后半部分链表交替合并
    struct ListNode *q = head, *nxt;
    while (p) {
        nxt = q->next;
        q->next = p;
        p = p->next;
        q->next->next = nxt;
        q = nxt;
    }
}

完整代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* reverse(struct ListNode* head) {
    struct ListNode *pre = NULL, *cur = head, *nxt;
    while (cur) {
        nxt = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nxt;
    }
    return pre;
}

void reorderList(struct ListNode* head) {
    if (!head || !head->next) {
        return;
    }
    
    // 使用快慢指针找出链表的中点
    struct ListNode *slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // 将后半部分链表反转
    struct ListNode *p = slow->next;
    slow->next = NULL;
    p = reverse(p);
    
    // 将前半部分链表和反转后的后半部分链表交替合并
    struct ListNode *q = head, *nxt;
    while (p) {
        nxt = q->next;
        q->next = p;
        p = p->next;
        q->next->next = nxt;
        q = nxt;
    }
}

时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。