数据结构链表（相关搜索：单链表）

Question

数据结构把我整不会了，有没有朋友帮我看看这段代码的问题，感激不尽！
题目：有一个整数单链表L，设计一个算法删除其中所有值为x节点，并给出算法的时间和空间复杂度。例如L=(1,2,2,3,1)，x=2,删除后L=(1,3,1)。

//问：有一个整数单链表L，设计一个算法删除其中所有值为x节点，并给出算法的时间和空间复杂度。例如L=(1,2,2,3,1)，x=2,删除后L=(1,3,1)。
//答：
#include<iostream>
using namespace std;

struct LinkedList
{
    int data;
    LinkedList* next;
};

void CreateList(LinkedList*& L, LinkedList*& head)
{
    LinkedList* tmp;
    L = new LinkedList();
    head = L;
    L->data = 1;
    tmp = new LinkedList();
    L->next = tmp;
    L = L->next;
    L->data = 2;
    tmp = new LinkedList();
    L->next = tmp;
    L = L->next;
    L->data = 2;
    tmp = new LinkedList();
    L->next = tmp;
    L = L->next;
    L->data = 3;
    tmp = new LinkedList();
    L->next = tmp;
    L = L->next;
    L->data = 1;
    tmp = new LinkedList();
    L->next = tmp;
    L = L->next;
    L->next = nullptr;
    delete tmp;
}
void Delete(LinkedList*& head, int del)
{
    LinkedList* prev = head;
    LinkedList* tmp;
    LinkedList* curr = prev->next;
    if (prev->data == del)
    {
        tmp = prev;
        prev = prev->next;
        head = prev;
        delete tmp;
    }
    while (curr->next != nullptr)
    {
        if (curr->data == del)
        {
            tmp = curr;
            prev->next = tmp->next;
            curr = curr->next;
            delete tmp;
        }
        else
        {
            prev = prev->next;
            curr = prev->next;
        }
    }
}

void PrintList(LinkedList* head)
{
    LinkedList* L = head;
    while (L->next != nullptr)
    {
        cout << L->data << " ";
        L = L->next;
    }
    cout << endl;
}
int main()
{
    int del = 2;
    LinkedList* L;
    LinkedList* head;
    CreateList(L,head);
    cout << "初始链表：";
    PrintList(head);
    Delete(head,del);
    cout << "删除元素"<<del<<"后的链表：";
    PrintList(head);
    delete head;
    
    return 0;
}

运行结果是这样的：

真的整不会了

Answer 1

Laurent_Zhu 上午好☀️☀️☀️️
本答案参考ChatGPT-3.5

问题的代码存在一些问题导致程序运行时出现错误。下面是对代码的问题进行分析和修改建议：

1. 在Delete函数中，判断链表中的节点值是否为要删除的值时，应该使用while循环而不是if条件语句。因为要删除的节点可能不止一个，需要遍历整个链表来找到所有的要删除的节点。

2. 在Delete函数的while循环中，应该先更新prev和curr指针的位置，然后再进行节点的删除操作。否则会导致删除节点后，prev和curr指针指向错误的位置。

3. 在Delete函数的while循环中，如果要删除的节点是最后一个节点，那么curr指针会指向最后一个节点的下一个节点nullptr，此时应该退出循环。

下面是修改后的代码：

void Delete(LinkedList*& head, int del)
{
    LinkedList* prev = head;
    LinkedList* tmp;
    LinkedList* curr = prev->next;
    if (prev->data == del)
    {
        tmp = prev;
        prev = prev->next;
        head = prev;
        delete tmp;
    }
    while (curr != nullptr)
    {
        if (curr->data == del)
        {
            tmp = curr;
            prev->next = curr->next;
            curr = curr->next;
            delete tmp;
        }
        else
        {
            prev = prev->next;
            curr = curr->next;
        }
    }
}

接下来是算法的时间和空间复杂度分析。

• 时间复杂度：该算法需要遍历整个链表，对于每个节点，最坏情况下需要删除，因此时间复杂度为O(n)，其中n为链表中的节点个数。

• 空间复杂度：除了原有的链表外，算法没有使用额外的空间，因此空间复杂度为O(1)。