C语言实现单链表拆分：偶数结点与奇数结点分离

本代码使用C语言实现将一个包含自然数结点的单链表拆分为两个单链表，原链表保留偶数结点，奇数结点按顺序组成新链表。

代码实现

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

// 定义链表结构体
typedef struct Node{
    int data;
    struct Node* next;
}Node;

// 定义函数，输入为原链表头结点，输出为保留偶数和奇数的两个链表的头结点
void splitList(Node* head, Node** evenHead, Node** oddHead){
    Node* current = head;
    Node* even = NULL;
    Node* odd = NULL;

    // 遍历链表
    while(current != NULL){
        if(current->data % 2 == 0){  // 如果当前结点的值为偶数
            if(even == NULL){  // 如果偶数链表为空，新建头结点
                even = current;
                *evenHead = even;
            }
            else{  // 否则将结点插入到偶数链表尾部
                even->next = current;
                even = even->next;
            }
        }
        else{  // 如果当前结点的值为奇数
            if(odd == NULL){  // 如果奇数链表为空，新建头结点
                odd = current;
                *oddHead = odd;
            }
            else{  // 否则将结点插入到奇数链表尾部
                odd->next = current;
                odd = odd->next;
            }
        }
        current = current->next;  // 指向下一个结点
    }
    // 将奇数链表尾部指向NULL，避免产生环
    if(odd != NULL){
        odd->next = NULL;
    }
    // 将偶数链表尾部指向NULL，避免产生环
    if(even != NULL){
        even->next = NULL;
    }
}

// 定义函数，输入为链表头结点，输出为链表长度
int getListLength(Node* head){
    int length = 0;
    Node* current = head;
    while(current != NULL){
        length++;
        current = current->next;
    }
    return length;
}

// 定义函数，输入为链表头结点和链表长度，输出为链表中结点的值
void printList(Node* head, int length){
    Node* current = head;
    for(int i=0; i<length; i++){
        printf('%d ', current->data);
        current = current->next;
    }
    printf('\n');
}

int main(){
    // 创建链表
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = 1;
    head->next = (Node*)malloc(sizeof(Node));
    head->next->data = 2;
    head->next->next = (Node*)malloc(sizeof(Node));
    head->next->next->data = 3;
    head->next->next->next = (Node*)malloc(sizeof(Node));
    head->next->next->next->data = 4;
    head->next->next->next->next = (Node*)malloc(sizeof(Node));
    head->next->next->next->next->data = 5;
    head->next->next->next->next->next = NULL;

    // 输出原链表
    int length = getListLength(head);
    printf("Original list: ");
    printList(head, length);

    // 拆分链表
    Node* evenHead = NULL;
    Node* oddHead = NULL;
    splitList(head, &evenHead, &oddHead);

    // 输出偶数链表
    int evenLength = getListLength(evenHead);
    printf("Even list: ");
    printList(evenHead, evenLength);

    // 输出奇数链表
    int oddLength = getListLength(oddHead);
    printf("Odd list: ");
    printList(oddHead, oddLength);

    // 释放内存
    free(head->next->next->next->next);
    free(head->next->next->next);
    free(head->next->next);
    free(head->next);
    free(head);
    return 0;
}

代码解释

1. splitList 函数：
   • 遍历原链表，判断当前结点值是否为偶数。
   • 如果为偶数，将其插入到 even 链表尾部。
   • 如果为奇数，将其插入到 odd 链表尾部。
   • 遍历结束后，将 even 和 odd 链表的尾部指向 NULL，避免产生环。
2. getListLength 函数：
   • 遍历链表，统计结点个数，返回链表长度。
3. printList 函数：
   • 遍历链表，输出每个结点的值。
4. main 函数：
   • 创建一个包含 5 个结点的单链表。
   • 调用 splitList 函数将链表拆分为偶数链表和奇数链表。
   • 调用 printList 函数分别输出原链表、偶数链表和奇数链表。
   • 释放所有分配的内存。

示例演示

Original list: 1 2 3 4 5 
Even list: 2 4 
Odd list: 1 3 5 

从输出结果可以看出，原链表中保留了偶数结点，而奇数结点组成了一个新链表。

总结

本文通过C语言代码实现了一个将单链表拆分为偶数结点链表和奇数结点链表的功能，并提供了详细的代码解释和示例演示。该代码可作为学习C语言单链表操作和数据结构算法的参考。