C语言实现：将链表中奇偶节点分别排序

在数据结构中，链表是一种常见的线性数据结构，由一系列节点组成。链表中的每个节点包含数据部分和指向下一个节点的指针。根据节点连接方式的不同，链表可以分为单向链表、双向链表和循环链表等类型。而在对链表进行操作时，往往需要编写特定的算法来处理节点间的关系。 在给定的文件信息中，我们看到了一个具体的操作要求：“奇数节点和偶数节点分别排在一起”。这一要求指的是将链表中奇数位置的节点排到一起，偶数位置的节点也排到一起，但是奇数节点和偶数节点的原始顺序需要保持不变。这可以通过多种方式实现，其中一种高效的方法是使用“原地”算法，即不需要额外分配大量空间来完成操作，而是通过调整链表中节点指针来达到目的。 具体到编写C语言代码，我们需要遵循以下步骤： 1. 定义链表节点的数据结构。 2. 实现链表的创建和初始化。 3. 编写函数，将奇数节点和偶数节点分开，保持原有顺序不变。 下面是一个简单的C语言代码实现过程： ```c #include <stdio.h> #include <stdlib.h> // 定义链表节点结构体 struct ListNode { int val; struct ListNode *next; }; // 创建新节点的函数 struct ListNode* createNode(int val) { struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode)); newNode->val = val; newNode->next = NULL; return newNode; } // 链表的插入函数，将节点按照顺序插入链表中 void insertNode(struct ListNode** head, int val) { struct ListNode* newNode = createNode(val); if (*head == NULL) { *head = newNode; } else { struct ListNode* temp = *head; while (temp->next != NULL) { temp = temp->next; } temp->next = newNode; } } // 函数：奇数节点和偶数节点分别排在一起 void reorderLinkedList(struct ListNode** head) { if (*head == NULL || (*head)->next == NULL) { return; } struct ListNode *odd = *head, *even = (*head)->next, *evenHead = even; // 分离奇数节点和偶数节点 while (even != NULL && even->next != NULL) { odd->next = even->next; odd = odd->next; even->next = odd->next; even = even->next; } odd->next = evenHead; } // 打印链表函数 void printList(struct ListNode* node) { while (node != NULL) { printf("%d ", node->val); node = node->next; } printf("\n"); } // 主函数测试以上代码 int main() { struct ListNode* head = NULL; insertNode(&head, 1); insertNode(&head, 2); insertNode(&head, 3); insertNode(&head, 4); insertNode(&head, 5); printf("Original List: "); printList(head); reorderLinkedList(&head); printf("Reordered List: "); printList(head); // 释放链表内存 struct ListNode* temp; while (head != NULL) { temp = head; head = head->next; free(temp); } return 0; } ``` 以上代码首先定义了链表节点的结构体，并实现了创建新节点、插入节点、奇偶节点分离、打印链表和释放链表内存的函数。在`main`函数中，我们创建了一个简单的链表并调用`reorderLinkedList`函数来重新排列链表，使奇数位置的节点和偶数位置的节点分别排在一起，同时保持各自的顺序不变。 在链表操作中，我们需要特别注意内存管理，尤其是避免内存泄漏。在上面的代码中，我们通过`free`函数在链表不再需要时释放了内存，以确保程序的健壮性。 以上代码实现了一个具体的链表操作算法，是算法与数据结构在C语言中的实际应用。通过这样的练习，可以加深对链表及其操作的理解，为解决更复杂的数据结构问题打下坚实的基础。