C语言实现单链表重新排列

要实现链表的重新排列，我们可以分为以下几个步骤：

1. 找到链表的中间节点：可以使用快慢指针的方法，快指针每次移动两步，慢指针每次移动一步，当快指针到达链表尾部时，慢指针指向的节点就是中间节点。

2. 将链表的后半部分反转：从中间节点开始，将链表后半部分的节点反转。

3. 合并两个链表：将反转后的后半部分链表插入到原链表的间隔位置，从而实现链表的重新排列。

以下是用C语言实现上述步骤的代码：

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

// 定义链表节点结构
typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// 创建新节点
ListNode* createNode(int val) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!
");
        exit(1);
    }
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 打印链表
void printList(ListNode* head) {
    ListNode* curr = head;
    while (curr != NULL) {
        printf("%d -> ", curr->val);
        curr = curr->next;
    }
    printf("NULL
");
}

// 反转链表
ListNode* reverseList(ListNode* head) {
    ListNode* prev = NULL;
    ListNode* curr = head;
    while (curr != NULL) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// 合并链表
void mergeLists(ListNode* head1, ListNode* head2) {
    ListNode* curr1 = head1;
    ListNode* curr2 = head2;
    while (curr1 != NULL && curr2 != NULL) {
        ListNode* next1 = curr1->next;
        ListNode* next2 = curr2->next;
        curr1->next = curr2;
        curr2->next = next1;
        curr1 = next1;
        curr2 = next2;
    }
}

// 重新排列链表
void reorderList(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return;
    }
    
    // 找到链表的中间节点
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // 反转链表的后半部分
    ListNode* secondHalf = reverseList(slow->next);
    slow->next = NULL;
    
    // 合并两个链表
    mergeLists(head, secondHalf);
}

// 销毁链表
void destroyList(ListNode* head) {
    ListNode* curr = head;
    while (curr != NULL) {
        ListNode* next = curr->next;
        free(curr);
        curr = next;
    }
}

int main() {
    // 创建示例链表：1 -> 2 -> 3 -> 4 -> 5 -> 6
    ListNode* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);
    head->next->next->next->next->next = createNode(6);

    printf("Before reordering: ");
    printList(head);

    // 重新排列链表
    reorderList(head);

    printf("After reordering: ");
    printList(head);

    // 销毁链表
    destroyList(head);

    return 0;
}

你可以将上述代码保存为一个后缀名为.c的文件，然后使用C语言编译器编译运行。程序将输出重新排列后的链表。在示例中，链表1->2->3->4->5->6将被重新排列为6->1->5->2->4->3。