Delete K nodes in a linked list having their data less than the next node's The question is from here.


  Given two numbers N and K where N is the number of nodes and K is the number of nodes to be deleted, delete K nodes whose data is less than their next node's data. If no such nodes exist, delete the last node.


But it is still giving me TLE. I tried all the optimisations that could occur to me. I know this can be done with stacks but I would like to know if it can't done in the allocated time with linked lists.

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

struct Node
{
    int value;
    struct Node *next;
};

void addnode(struct Node** head, struct Node** tail, int data)
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp-&gt;value = data;
    temp-&gt;next = nullptr;
    if( *head == nullptr)
    {
        *head = temp;
        *tail = *head;
        return;
    }
    (*tail)-&gt;next = temp;
    *tail = temp;
}

void deleteNode(struct Node** head, struct Node** prev, struct Node** temp)
{
    if( (*prev)-&gt;next == *head)
    {
        *head = (*prev)-&gt;next-&gt;next;
        return;
    }
    (*prev)-&gt;next = (*temp)-&gt;next;
}

void deletenodeatlast(struct Node** prev)
{
    (*prev)-&gt;next = (*prev)-&gt;next-&gt;next; 
}

void display(struct Node* head)
{
    struct Node* p = head;
    while(p != nullptr)
    {
        printf("%d ", p-&gt;value);
        p = p-&gt;next;
    }
    printf("\n");
}

int main()
{
    int T;
    scanf("%d", &amp;T);
    while(T--)
    {
        struct Node* head = nullptr;
        struct Node* tail = head;
        int N, K;
        scanf("%d %d", &amp;N, &amp;K);

        for(int i = 0; i &lt; N; i++)
        {
            int data;
            scanf("%d", &amp;data);
            addnode(&amp;head, &amp;tail, data);
        }
        for(int i = 0; i &lt; K; i++)
        {
            bool isGreater = false;
            struct Node* p = head;
            struct Node* prev = (struct Node*)malloc(sizeof(struct Node));
            prev-&gt;value = 1000000;
            prev-&gt;next = p;

            while( p-&gt;next != nullptr)
            {
                if( p-&gt;value &lt; p-&gt;next-&gt;value)
                {
                    deleteNode(&amp;head, &amp;prev, &amp;p);
                    isGreater = true;
                }
                else
                {
                    prev = p;
                    p = p-&gt;next;
                }

                if( isGreater )
                {
                    break;
                }
            }
            if( !isGreater)
            {
                deletenodeatlast(&amp;prev);
            }
        }
        display(head);
    }
    return 0;
}
Do you know Shlemiel The Painter?
He never moves his paint can, and so repeatedly walks all over the town.

What you need to do is take the algorithm for removing one friend, look at how it works when applied k times, and then cut out all the redundant Setup work.



Aside from that, you aren't using any C++ containers or algorithms, nor smart-pointers (std::unique_ptr), new or the like.

Don't assume nothing will go wrong. While it is unlikely with malloc() as long as you stay reasonable, scanf() parses user-input, and users will do everything possible, even if you think it's impossible.

There's more, but that should be a good start.