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

e37o9pze 于 2023-10-21 发布在其他

关注(0)|答案(1)|浏览(95)

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

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++

来源：https://stackoverflow.com/questions/77283045/why-the-original-linked-list-is-getting-lost-after-passing-as-a-argument-in-reve

1条答案

按热度按时间

xxslljrj1#

原来的链表丢失了，因为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;
}

赞(0）回复(0）举报 2023-10-21

我来回答

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

1条答案

相关问题

热门标签

最新问答