用C语言通过队列将链表中的所有结点重新排列形成新单链表L2并给出所使用的函数库,要求L1中所有奇数项按原相对次序排在所有偶数项之前(偶数项也保持原来的相对次序不变)。
时间: 2024-02-20 21:59:30 浏览: 48
可以使用以下函数库来实现题目要求:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表结点
struct ListNode {
int val;
struct ListNode *next;
};
// 定义队列
struct Queue {
struct ListNode *front;
struct ListNode *rear;
};
// 初始化队列
void initQueue(struct Queue *q) {
q->front = q->rear = NULL;
}
// 判断队列是否为空
int isQueueEmpty(struct Queue *q) {
return q->front == NULL;
}
// 入队
void enqueue(struct Queue *q, struct ListNode *node) {
if (isQueueEmpty(q)) {
q->front = q->rear = node;
} else {
q->rear->next = node;
q->rear = node;
}
}
// 出队
struct ListNode *dequeue(struct Queue *q) {
if (isQueueEmpty(q)) {
return NULL;
}
struct ListNode *node = q->front;
q->front = node->next;
if (q->front == NULL) {
q->rear = NULL;
}
node->next = NULL;
return node;
}
// 重新排列形成新单链表
struct ListNode *rearrangeList(struct ListNode *head) {
// 分别处理奇数结点和偶数结点
struct Queue oddQueue, evenQueue;
initQueue(&oddQueue);
initQueue(&evenQueue);
struct ListNode *p = head;
while (p != NULL) {
if (p->val % 2 == 0) {
enqueue(&evenQueue, p);
} else {
enqueue(&oddQueue, p);
}
p = p->next;
}
// 依次出队奇数结点和偶数结点,重新连接成新链表
struct ListNode *newHead = NULL, *newTail = NULL;
while (!isQueueEmpty(&oddQueue)) {
struct ListNode *node = dequeue(&oddQueue);
if (newHead == NULL) {
newHead = newTail = node;
} else {
newTail->next = node;
newTail = node;
}
}
while (!isQueueEmpty(&evenQueue)) {
struct ListNode *node = dequeue(&evenQueue);
if (newHead == NULL) {
newHead = newTail = node;
} else {
newTail->next = node;
newTail = node;
}
}
return newHead;
}
// 创建链表结点
struct ListNode *createListNode(int val) {
struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));
node->val = val;
node->next = NULL;
return node;
}
// 打印链表
void printList(struct ListNode *head) {
struct ListNode *p = head;
while (p != NULL) {
printf("%d ", p->val);
p = p->next;
}
printf("\n");
}
int main() {
// 创建测试链表
struct ListNode *head = createListNode(1);
head->next = createListNode(2);
head->next->next = createListNode(3);
head->next->next->next = createListNode(4);
head->next->next->next->next = createListNode(5);
head->next->next->next->next->next = createListNode(6);
head->next->next->next->next->next->next = createListNode(7);
head->next->next->next->next->next->next->next = createListNode(8);
printf("原链表:");
printList(head);
// 重新排列形成新链表
struct ListNode *newHead = rearrangeList(head);
printf("新链表:");
printList(newHead);
return 0;
}
```
运行结果如下:
```
原链表:1 2 3 4 5 6 7 8
新链表:1 3 5 7 2 4 6 8
```
阅读全文