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

问：

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

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/

C++ 算法列表反向回文

注意：如果使用双向链表，则可以从列表的两端开始进行比较（如果第一个和最后一个相同，则先向前移动一个节点，最后一个向后移动一个节点，然后再次测试。如果不相同，则返回 false）到中心，而不必浪费时间和资源来反转列表，然后比较整个事情。

答：

1赞 luckygem 10/13/2023 #1

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

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;
}

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

Why the original Linked List is getting lost after passing as a argument in reverse function

评论

评论