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

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，注释块中的代码就会失败。我能理解为什么它会失败，因为 temp 和 ptr 都持有 1332 并且 else if 在第二次迭代中返回 false，但我找不到任何解决方案。此外，函数所在的文件已在函数定义上方进行了注释。有帮助吗？

Answer 1

据我所知，你的代码的第一部分有问题：在单链表中找到第二大元素。

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

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

找到两个最大值的算法的工作原理如下：

初始化：用可能的最低值或特殊的"uninitialized"标志初始化两个当前最大值。
在所有元素上循环：
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）。

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

Deletion of second largest element from a singly linked list

c

c++

linked-list

data-structures

singly-linked-list