c++ - 从单链表中删除第二大元素

Question

我目前正在尝试为自己编写一个数据结构框架。从单链表中删除第二大节点在一般情况下是完美的。但是在特定的方面失败了。这是我已经尝试过的:

//node.h
typedef struct Node {
    int value;
    struct Node *nextNode;
} Node;

//linkedlist.h
typedef struct LinkedList{
    Node *head;
    int count;
} LinkedList;

//liblinkedlist.c
int deleteSecondLargest(LinkedList *list){
    if(list->count==0)
        return 1;
    if(list->count==1)
        return 2;
    Node *temp = list->head;
    Node *largest = temp;
    Node *prev = NULL;
    Node *prev1 = NULL;
    Node *ptr = temp;

    //finding the second largest node
    while(temp!=NULL){
        if(temp->value > largest->value){
            largest = temp;
        }
        else if((temp->value!=largest->value) && (temp->value > ptr->value)){//here's the code failing
            prev1 = prev;
            ptr = temp;
        }
        prev = temp;
        temp = temp->nextNode;
    }

    //deleting it
    if(ptr==list->head)
        list->head = list->head->nextNode;
    else
        prev1->nextNode = ptr->nextNode;
    free(ptr);
    list->count--;
    return 0;
}

只要列表中的项目顺序为 1332->34->N，代码在注释 block 中就会失败。 我能理解为什么它会失败，因为 temp 和 ptr 都持有 1332 而 else if 在第二次迭代中返回 false，但我可以'找到任何解决方案。此外，函数所在的文件已在函数定义上方进行了注释。 有帮助吗？

Answer 1

据我所知，您的代码的第一部分存在问题:在单链表中查找第二大元素。

其实这段代码存在三个问题:

1. ptr 用第一个元素初始化，它可能太大而不能成为第二个最大值。
2. 没有节点从largest 降级到ptr。这意味着，对于列表 34 ​​-> 1332 -> N，您的代码也不起作用。
3. 如果两个最大值具有相等的值，则忽略第二个。这意味着，对于列表 123 -> 123 -> N，您的代码也不起作用。

寻找两个最大值的算法的工作原理如下:

1. 初始化:用可能的最低值或特殊的“未初始化”标志初始化两个当前最大值。
2. In 遍历所有元素:
   1. 使用当前值更新两个最大值。

实现:

// Initialization
Node *largest = nullptr; // for maximum, nullptr means "not initialized"
Node *largest2 = nullptr; // for second maximum, nullptr means "not initialized"
Node *prev_largest = nullptr; // for previous node for maximum
Node *prev_largest2 = nullptr; // for previous node for second maximum

// Iterations
for (Node *cur = list->head, *prev = nullptr; // start of the loop: current node is head, prev is null
    cur != nullptr; // end of the loop: current node is null
    prev = cur, cur = cur->nextNode) { // loop iteration: move both current and prev nodes forward

    if (largest == nullptr || cur->value > largest->value) { // check if we need to update maximum
        // the node which was maximum is now second maximum
        prev_largest2 = prev_largest;
        largest2 = largest;
        // current node is now maximum
        prev_largest = prev;
        largest = cur;
    } else if (largest2 == nullptr || cur->value > largest2->value) { // check if we need to update second maximum
        // current node is now second maximum
        prev_largest2 = prev;
        largest2 = cur;
    }
}
// End of algorithm
// Second maximum is now in variable largest2
// Previous node for second maximum is now in variable prev_largest2

此外，请注意，即使您的列表包含的元素少于 2 个，此算法也能正常工作(在这种情况下，largest2 将在末尾为 nullptr)。