Deletion of second largest element from a singly linked list

Question

I'm currently trying to write a data structure framework for myself. Deletion of the second largest node from a singly linked list works flawlessly in ordinary cases. But fails in a particular one. Here's what I've already tried :

//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;
}

The code fails in the commented block whenever the items in the list are in the order of 1332->34->N. I can understand why it is failing because both temp and ptr is holding 1332 and else if is returning false in the second iteration, but I can't find any solution to it. Also, the files in which the functions reside has been commented above the function definition. Any help?

Answer 1

As far as I see, you have a problem with the first part of your code: finding the second-largest element in a single-linked list.

In fact, there're three problems in this code:

1. The ptr is initialized with first element, which may be too large to be the second maximum.
2. No node is ever demoted from largest to ptr. That means, for list 34 -> 1332 -> N your code also does not work.
3. If two maximums have equal values, second one is ignored. That means, for list 123 -> 123 -> N your code also does not work.

The algorithm of finding two maximums works as follows:

1. Initialization: initialize two current maximums with the lowest possible values or special "uninitialized" flag.
2. In loop over all the elements:
   3. Update both maximums using the current value.

Implementation:

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

Also, please note this algorithm works even if your list contains less than 2 elements (in this case largest2 will be nullptr at the end).