c++ - 为什么链表重新排序失败？

Question

在这段代码中，我尝试使用 evenOdd() 函数修改列表，使偶数出现在列表的最前面，奇数出现在列表的最后。
但是没有得到预期的输出，帮帮我。

预期输出:

订购前:
1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7 --> 空
订购后:
2 --> 4 --> 6 --> 1 --> 3 --> 5 --> 7 --> 空

实际输出:

1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7 --> 空

#include<iostream>
using namespace std;

class Node
{
public:
    int data;
    Node* next;
};

void addEnd(Node **head, int val)
{
    Node *temp=*head;
    Node *newnode=new Node();
    newnode->data=val;
    newnode->next=NULL;
    if(*head == NULL) {*head = newnode; return;}
    while(temp->next!=NULL) {temp=temp->next;}
    temp->next=newnode;
}

void deleteKey(Node **head,int val)
{
    Node *temp=*head;
    Node* prev;
    if(temp!=NULL and temp->data == val)
    {
        *head = temp->next;
        delete temp;
        return;
    }
    while(temp->next!=NULL)
    {
        if(temp->data == val) {prev = temp; break;}
        prev=temp;
        temp=temp->next;
    }
    if(temp->data != val) {cout<<"NO SUCH VAlUES"; return;}
    prev->next=temp->next;
}

void evenOdd(Node **head)
{
    Node *temp = *head;
    while(temp != NULL)
    {
        if(temp->data%2 == 1)
        {addEnd(*(&head),temp->data); deleteKey(*(&head),temp->data);}
        temp = temp->next;
    }
}

void printList(Node *node)
{
    while(node!=NULL)
    {
        cout<<"  "<<node->data<<" --> ";
        node=node->next;
    }
    cout<<"NULL";
}

int main()
{
    Node *head = NULL;
    addEnd(&head,1);
    addEnd(&head,2);
    addEnd(&head,3);
    addEnd(&head,4);
    addEnd(&head,5);
    addEnd(&head,6);
    addEnd(&head,7);
    cout<<"Before Ordering :\n";
    printList(head);
    evenOdd(&head);
    cout<<"After Ordering :\n";
    printList(head);
    return 0;
}

Answer 1

有了这个组合

if(temp->data%2 == 1)

和

deleteKey(*(&head),temp->data);

您正在删除当前正在查看的节点。包括一个实际的

delete temp;

在 deleteKey 中。

但随后您可以在此处访问刚刚删除的内存

temp = temp->next;

在 evenOdd 中。

在那之后，所有赌注都取消了。

但观察到的问题是在 deleteKey 内部引起的:

prev->next=temp->next; 

它使用 prev，其值与 temp 相同。
IE。它不会改变温度，尤其是指向温度的指针。
为此，您需要跟踪指向要删除的节点的指针，并更改它。
变量的命名表明你知道这个概念并尝试在这里做

{prev = temp; break;}

但很明显，那不能取回指针。
您需要一直更新 prev，然后像这样的内容需要包含在您的删除代码中

{prev->next = temp->next; break;} /* prev->next currently points to temp, but prev!= temp */
/* update the "next" pointing to current node so that it points to the next one */

您可能会发现我的其他答案对于分析此类问题很有用:
Tricks to analyse pointer and pointer-to-pointer structures in C?