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

Question

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

预期输出：

订购前：
1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7 --> NULL
订购后：
2 --> 4 --> 6 --> 1 --> 3 --> 5 --> 7 --> NULL

实际输出：

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

#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 */

您可能会发现我的其他回答对分析此类问题很有用：

Answer 2

在 evenOdd 函数中 temp 指向插入在后面的节点，而根据迭代它应该指向第 2、3、4 个节点。所以当你执行 temp = temp->next 时，它会溢出。

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

Why does reordering of linked list fail?

c++

data-structures

singly-linked-list