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

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

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

实际上，此代码中存在三个问题：

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

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

1. 初始化：使用尽可能低的值或特殊的"未初始化"标志初始化两个电流最大值。
2. 循环遍历所有元素：
   3. 使用当前值更新两个最大值。

实现：

// 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)，此算法也有效。