用c语言写程序 【问题描述】: 设线性表L = (a1 ,a2,a3,.…,an-1,an)采用带头结点的单链表保存,请设计一个空间复杂度为 0(1)且时间上尽可能高效的算法,重新排列 L 中的各结点,得到线性表S= (a1,an,a2,an-1,.…)。 【输入形式】:多组数据,每组第一行为n,表示链表的长度。接下来为链表中的元素。不超过5组数据。 【输出形式】:每组数据,输出重新排列后的序列。 【样例输入】 10 11 13 15 17 19 2 4 6 8 20 【样例输出】 11 20 13 8 15 6 17 4 19 2
时间: 2023-05-29 19:04:44 浏览: 73
#include<stdio.h>
#include<stdlib.h>
typedef struct ListNode{ //定义链表结构体
int val;
struct ListNode* next;
}ListNode;
void reorderList(ListNode* head) {
if(head == NULL || head->next == NULL || head->next->next == NULL) return; //链表为空或长度小于等于2,不需要重新排列
ListNode* slow = head->next;
ListNode* fast = head->next;
while(fast->next != NULL && fast->next->next != NULL){ //快慢指针找到链表中点
slow = slow->next;
fast = fast->next->next;
}
ListNode* mid = slow->next; //将链表从中点处断开
slow->next = NULL;
ListNode* prev = NULL;
ListNode* curr = mid;
ListNode* next = NULL;
while(curr != NULL){ //将后半部分链表反转
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
ListNode* p1 = head->next; //将前后两个链表交替合并
ListNode* p2 = prev;
while(p1 != NULL && p2 != NULL){
ListNode* tmp1 = p1->next;
ListNode* tmp2 = p2->next;
p1->next = p2;
p2->next = tmp1;
p1 = tmp1;
p2 = tmp2;
}
}
int main(){
int n;
while(scanf("%d",&n) != EOF){
ListNode* head = (ListNode*)malloc(sizeof(ListNode)); //建立带头结点的链表
head->next = NULL;
ListNode* p = head;
for(int i = 0; i < n; i++){
int num;
scanf("%d",&num);
ListNode* node = (ListNode*)malloc(sizeof(ListNode)); //新建结点
node->val = num;
node->next = NULL;
p->next = node;
p = p->next;
}
reorderList(head); //重新排列链表
p = head->next;
while(p != NULL){ //输出排列后的链表
printf("%d ",p->val);
p = p->next;
}
printf("\n");
}
return 0;
}
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)