C++链表反转复制函数运行时错误排查：回文判断前置问题

Hey there! Let's break down the issues in your code step by step, since you're trying to check if a linked list is a palindrome without losing the original list.

核心错误：createReversedLinkedList函数的问题 #

这是你遇到运行时错误的根源，有两个关键问题：

1. 单节点链表处理逻辑错误 #

在createReversedLinkedList中，当原链表只有一个节点时，你返回了NULL，但正确的行为应该是返回一个复制后的单个节点（反转单个节点的链表还是它自己）。这个错误会导致单节点输入直接得到空指针，后续操作必然崩溃。

2. 复制链表时的死循环 #

在复制原链表的while循环里，你没有更新temp指针的位置——temp一直停留在原链表的头节点，导致程序无限创建新节点，最终引发内存溢出的运行时错误。必须在每次循环末尾加上temp = temp->next;来遍历原链表。

次要问题：check_palindrome函数的潜在隐患 #

1. 原链表被破坏：你最初用returnReverseLinkedList反转链表，但这个函数是原地反转，会直接修改原链表的结构，导致original指针指向的原链表已经被打乱，后续的对比完全错误。这也是你需要createReversedLinkedList的原因，但之前的函数出错了。
2. 循环条件错误：你的循环条件original->next != NULL || reverse->next != NULL会导致空指针访问，正确的条件应该是当original和reverse都不为NULL时才继续对比。

修正后的完整代码 #

#include <iostream>
using namespace std;

class node {
public:
    int data;
    node *next;
    node(int data) {
        this->data = data;
        this->next = NULL;
    }
};

// 原地反转链表（会修改原链表，仅用于反转副本）
node *returnReverseLinkedList(node *head) {
    if (head == NULL || head->next == NULL)
        return head;
    node *prev = NULL;
    node *curr = head;
    node *tempNext = head->next;
    while (tempNext != NULL) {
        curr->next = prev;
        prev = curr;
        curr = tempNext;
        tempNext = tempNext->next;
    }
    curr->next = prev;
    return curr;
}

// 复制原链表并反转副本，保留原链表
node *createReversedLinkedList(node *head) {
    if (head == NULL)
        return NULL;
    // 处理单节点链表，返回复制后的节点
    if (head->next == NULL) {
        return new node(head->data);
    }
    node *temp = head;
    node *newHead = NULL;
    node *newTail = NULL;
    while (temp != NULL) {
        node *newNode = new node(temp->data);
        if (newHead == NULL) {
            newHead = newNode;
            newTail = newNode;
        } else {
            newTail->next = newNode;
            newTail = newNode;
        }
        // 关键：移动temp指针遍历原链表
        temp = temp->next;
    }
    // 反转复制后的链表
    return returnReverseLinkedList(newHead);
}

// 正确的回文判断函数
bool check_palindrome(node *head) {
    if (head == NULL || head->next == NULL)
        return true;
    // 获取原链表的反转副本
    node *reverse = createReversedLinkedList(head);
    node *original = head;
    // 循环条件：两个指针都不为空时对比
    while (original != NULL && reverse != NULL) {
        if (original->data != reverse->data) {
            // 实际项目中记得释放反转链表的内存，避免泄漏
            return false;
        }
        original = original->next;
        reverse = reverse->next;
    }
    // 释放反转链表内存（可选，但属于良好编程习惯）
    return true;
}

node *takeinput() {
    int data;
    cin >> data;
    node *head = NULL, *tail = NULL;
    while (data != -1) {
        node *newnode = new node(data);
        if (head == NULL) {
            head = newnode;
            tail = newnode;
        } else {
            tail->next = newnode;
            tail = newnode;
        }
        cin >> data;
    }
    return head;
}

void print(node *head) {
    node *temp = head;
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

int main() {
    node *head = takeinput();
    node *reverse2 = createReversedLinkedList(head);
    cout << "Original list: ";
    print(head);
    cout << "Reversed copy: ";
    print(reverse2);
    
    bool ans = check_palindrome(head);
    if (ans)
        cout << "true";
    else
        cout << "false";
    
    // 可添加函数释放链表内存，避免内存泄漏
    return 0;
}

额外优化提示 #

1. 内存泄漏处理：上面的代码创建了反转副本但未释放内存，实际开发中应该添加deleteLinkedList辅助函数来释放所有节点的内存。
2. 空间优化：复制整个链表再反转的方法空间复杂度为O(n)。如果想优化，可以用快慢指针找到链表中点，反转后半部分后与前半部分对比，这样空间复杂度可降到O(1)，需要注意奇数/偶数长度链表的中点处理。

内容的提问来源于stack exchange，提问作者user11555625