面试题：C语言循环链表的复杂删除操作

Question

给定一个C语言实现的循环链表，节点结构体为：struct Node { int data; struct Node *next; }。编写一个函数，删除链表中所有数据值为偶数的节点，并且处理好循环链表的循环特性，确保链表在操作后仍然是正确的循环链表。要求函数接收链表头指针作为参数，并返回处理后的链表头指针。

Answer 1

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

struct Node {
    int data;
    struct Node *next;
};

struct Node* deleteEvenNodes(struct Node *head) {
    if (head == NULL) {
        return NULL;
    }
    struct Node *prev = head;
    struct Node *curr = head->next;
    while (curr != head) {
        if (curr->data % 2 == 0) {
            prev->next = curr->next;
            free(curr);
            curr = prev->next;
        } else {
            prev = curr;
            curr = curr->next;
        }
    }
    if (head->data % 2 == 0) {
        if (head == head->next) {
            free(head);
            return NULL;
        } else {
            prev->next = head->next;
            free(head);
            return prev->next;
        }
    }
    return head;
}