判断链表是否回文


bool isPail(ListNode* head) {
        std::stack<int> st;

        // Push all elements of the linked list into the stack
        ListNode* current = head;
        while (current) {
            st.push(current->val);
            current = current->next;
        }

        // Compare elements from the stack with the elements in the linked list
        current = head;
        while (current) {
            if (current->val != st.top()) {
                return false;
            }
            st.pop();
            current = current->next;
        }

        return true;
}

统统压入一个栈，然后弹栈，和链表比较，如果 val 的数据类型比较大的话，压指针也是可以的。

C 的话用数组模拟一个栈也可以，不过申请空间的时候注意题干中数据大小范围，或者简单实现一个栈。

上面是我自己写的，这个时间复杂度是 O(n)，空间复杂度也是 O(n)。

如果可以破坏原链表的结构，那更好的解法是，时间复杂度 O(n)，空间复杂度 O(1)，运用快慢指针：

利用快慢指针，快指针一次进2步，慢指针一次进1步；

当快指针达到末尾，慢指针为中间节点；

反转慢指针开始的链表 →
反转单向链表；

一起遍历对比；

参考代码


#include <stdio.h>
#include <stdbool.h>

// 链表节点结构
struct ListNode {
    int val;
    struct ListNode *next;
};

// 反转链表函数
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *prev = NULL;
    struct ListNode *current = head;
    struct ListNode *next;

    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    return prev;
}

// 判断回文链表函数
bool isPalindrome(struct ListNode* head) {
    if (head == NULL || head->next == NULL)
        return true;

    struct ListNode *slow = head;
    struct ListNode *fast = head;

    // 使用快慢指针找到链表的中间节点
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 反转后半部分的链表
    struct ListNode *reversedSecondHalf = reverseList(slow->next);

    // 逐个比较前半部分和反转后的后半部分
    struct ListNode *p1 = head;
    struct ListNode *p2 = reversedSecondHalf;
    while (p2 != NULL) {
        if (p1->val != p2->val)
            return false;
        p1 = p1->next;
        p2 = p2->next;
    }

    return true;
}

// 测试函数
int main() {
    // 创建链表: 1 -> 2 -> 3 -> 2 -> 1
    struct ListNode node1 = {1, NULL};
    struct ListNode node2 = {2, NULL};
    struct ListNode node3 = {3, NULL};
    struct ListNode node4 = {2, NULL};
    struct ListNode node5 = {1, NULL};
    node1.next = &node2;
    node2.next = &node3;
    node3.next = &node4;
    node4.next = &node5;

    if (isPalindrome(&node1)) {
        printf("链表是回文链表\n");
    } else {
        printf("链表不是回文链表\n");
    }

    return 0;
}