c语言

如何使用C语言进行回文链表的验证

小樊
82
2024-04-26 17:01:04
栏目: 编程语言

可以通过以下步骤使用C语言进行回文链表的验证:

  1. 定义链表节点结构体,包括节点值和指向下一个节点的指针。
  2. 创建一个函数来反转链表,将链表的顺序倒转。
  3. 创建一个函数来验证链表是否为回文链表。可以使用快慢指针的方法找到链表中点,然后将链表分为两部分并反转其中一部分,最后比较两部分是否相同。
  4. 在主函数中创建一个链表,并调用验证函数来判断链表是否为回文链表。

下面是一个示例代码:

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

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

Node* reverseList(Node* head) {
    Node* prev = NULL;
    Node* current = head;
    Node* next = NULL;
    
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    
    return prev;
}

int isPalindrome(Node* head) {
    if (head == NULL || head->next == NULL) {
        return 1;
    }
    
    Node* slow = head;
    Node* fast = head;
    
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    Node* secondHalf = reverseList(slow->next);
    Node* firstHalf = head;
    
    while (secondHalf != NULL) {
        if (firstHalf->data != secondHalf->data) {
            return 0;
        }
        firstHalf = firstHalf->next;
        secondHalf = secondHalf->next;
    }
    
    return 1;
}

int main() {
    Node* head = NULL;
    Node* temp = NULL;
    
    // 创建一个示例链表 1->2->3->2->1
    head = (Node*)malloc(sizeof(Node));
    head->data = 1;
    
    temp = (Node*)malloc(sizeof(Node));
    temp->data = 2;
    head->next = temp;
    
    temp = (Node*)malloc(sizeof(Node));
    temp->data = 3;
    head->next->next = temp;
    
    temp = (Node*)malloc(sizeof(Node));
    temp->data = 2;
    head->next->next->next = temp;
    
    temp = (Node*)malloc(sizeof(Node));
    temp->data = 1;
    head->next->next->next->next = temp;
    head->next->next->next->next->next = NULL;
    
    if (isPalindrome(head)) {
        printf("The linked list is a palindrome.\n");
    } else {
        printf("The linked list is not a palindrome.\n");
    }
    
    return 0;
}

上面的代码中,首先定义了链表节点结构体,然后创建了一个函数来反转链表。接着定义了验证链表是否为回文链表的函数,并在主函数中创建了一个示例链表来测试。最后输出验证结果。

0
看了该问题的人还看了