为什么原始链表在反向函数中作为参数传递后会丢失

Question

当我尝试反转原始链表时，它在函数调用后丢失了。为什么会这样？

Node *reverse(Node *head)
{
    Node *prevNode = NULL, *currNode = head;
    while (currNode != NULL)
    {
        Node *nextNode = currNode->next;
        currNode->next = prevNode;
        prevNode = currNode;
        currNode = nextNode;
    }
    return prevNode;
}

bool isPalindrome(Node *head)
{
    Node *temp = head;
    Node *reversedList = reverse(temp);
    temp = head;
    while (temp != NULL)
    {
        if (temp->data != reversedList->data)
        {
            return false;
        }
        temp = temp->next;
        reversedList = reversedList->next;
    }
    return true;
}

// https://leetcode.com/problems/palindrome-linked-list/

Answer 1

原来的链表丢失了，因为reverse函数修改了它。要在不丢失原始列表的情况下检查回文，请在反转列表之前对其进行深层复制。然后，将原始列表与反向深拷贝进行比较。 试试这个：

Node *deepCopy(Node *head) {
    Node *newHead = NULL, *tail = NULL;

    while (head != NULL) {
        Node *newNode = new Node(head->data);
        if (newHead == NULL) {
            newHead = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
        head = head->next;
    }

    return newHead;
}

bool isPalindrome(Node *head) {
    Node *original = head;
    Node *reversed = reverse(deepCopy(head));

    while (original != NULL && reversed != NULL) {
        if (original->data != reversed->data) {
            return false;
        }
        original = original->next;
        reversed = reversed->next;
    }

    return true;
}