链表重排：将单链表重新排列为 Ln→L1→Ln−1→L2→⋯

链表重排：将单链表重新排列为 Ln→L1→Ln−1→L2→⋯

给定一个单链表 L1→L2→⋯→Ln−1→Ln，请编写程序将链表重新排列为 Ln→L1→Ln−1→L2→⋯。例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。

输入格式

每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数，即正整数N (≤10^10)。结点的地址是5位非负整数，NULL地址用−1表示。

接下来有N行，每行格式为：

Address Data Next

其中 Address是结点地址；Data是该结点保存的数据，为不超过105的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。

输出格式

对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

输入样例

00100 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

输出样例

68237 6 00100
00100 1 99999
99999 5 12309
12309 2 00000
00000 4 33218
33218 3 -1

C语言实现内容

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

struct ListNode {
    int address;
    int data;
    int next;
    struct ListNode *nextNode;
};

void reorderList(struct ListNode *head) {
    if (head == NULL || head->nextNode == NULL || head->nextNode->nextNode == NULL) {
        return;
    }
    
    struct ListNode *fast = head->nextNode;
    struct ListNode *slow = head->nextNode;
    
    while (fast != NULL && fast->nextNode != NULL) {
        slow = slow->nextNode;
        fast = fast->nextNode->nextNode;
    }
    
    struct ListNode *secondHalf = slow->nextNode;
    slow->nextNode = NULL;
    
    struct ListNode *prev = NULL;
    struct ListNode *cur = secondHalf;
    
    while (cur != NULL) {
        struct ListNode *next = cur->nextNode;
        cur->nextNode = prev;
        prev = cur;
        cur = next;
    }
    
    struct ListNode *firstHalf = head->nextNode;
    struct ListNode *p1 = firstHalf;
    struct ListNode *p2 = prev;
    
    while (p2 != NULL) {
        struct ListNode *next1 = p1->nextNode;
        struct ListNode *next2 = p2->nextNode;
        
        p1->nextNode = p2;
        p2->nextNode = next1;
        
        p1 = next1;
        p2 = next2;
    }
}

int main() {
    int N;
    scanf('%d', &N);
    
    struct ListNode *list[N];
    for (int i = 0; i < N; i++) {
        list[i] = (struct ListNode *)malloc(sizeof(struct ListNode));
        scanf('%d %d %d', &(list[i]->address), &(list[i]->data), &(list[i]->next));
        list[i]->nextNode = NULL;
    }
    
    for (int i = 0; i < N; i++) {
        struct ListNode *node = list[i];
        if (node->next != -1) {
            node->nextNode = list[node->next];
        }
    }
    
    struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
    dummy->nextNode = list[0];
    reorderList(dummy);
    
    struct ListNode *p = dummy->nextNode;
    while (p != NULL) {
        printf('%05d %d ', p->address, p->data);
        if (p->nextNode != NULL) {
            printf('%05d\n', p->nextNode->address);
        } else {
            printf('-1\n');
        }
        p = p->nextNode;
    }
    
    return 0;
}

该代码使用链表的快慢指针法将链表分成两半，并将后半部分反转。然后，依次将两个链表的节点交叉连接起来，实现链表重新排列。

希望对你有帮助！