C语言实现链表奇偶节点分离排序方法

资源摘要信息:"奇偶链表重排" 在编程领域中，链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。在某些应用场景中，需要对链表中的节点按照特定的规则重新排列，例如，将链表中的奇数节点和偶数节点分别排在一起。这个问题在面试中经常被提及，要求应聘者编写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; } // 重排链表，使得奇数位置的节点在前，偶数位置的节点在后 struct ListNode* reorderList(struct ListNode* head) { struct ListNode *odd = head, *even = head->next, *evenHead = even; // 分离奇偶节点链表 while (even != NULL && even->next != NULL) { odd->next = odd->next->next; even->next = even->next->next; odd = odd->next; even = even->next; } // 将偶数链表的末尾连接到null odd->next = NULL; // 将偶数链表反转 even = reverseList(evenHead); // 合并奇数链表和偶数链表 odd = head; while (even != NULL) { struct ListNode* temp = odd->next; odd->next = even; even = even->next; odd->next->next = temp; odd = temp; } return head; } // 辅助函数：反转链表 struct ListNode* reverseList(struct ListNode* head) { struct ListNode *prev = NULL, *curr = head, *next = NULL; while (curr != NULL) { next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } // 打印链表 void printList(struct ListNode* head) { struct ListNode* temp = head; while (temp != NULL) { printf("%d ", temp->val); temp = temp->next; } printf("\n"); } // 主函数 int main() { // 创建并初始化链表 struct 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); printf("Original list: "); printList(head); // 重排链表 head = reorderList(head); printf("Reordered list: "); printList(head); // 释放链表内存 // ... return 0; } ``` 在上述代码中，我们首先定义了链表节点的结构体`ListNode`，并提供了创建新节点、打印链表和反转链表的辅助函数。`reorderList`函数是实现奇偶链表重排的核心函数。首先，通过两次遍历分别构建奇数链表和偶数链表，并将偶数链表反转。然后，将反转后的偶数链表连接到奇数链表的末尾，从而实现重排。 在实际应用中，还需要注意内存管理，即在不再需要链表时，要逐个释放节点所占用的内存空间，以避免内存泄漏。 通过上述知识点，我们可以了解到，在解决奇偶链表重排问题时，不仅需要掌握链表的基本操作，如创建、遍历和打印，还需要熟悉链表的高级操作，例如链表的反转和内存管理。在编写C语言代码时，也需要关注代码的健壮性，避免出现内存泄漏等问题。