CODEWITHSUNDEEP
c++algorithmrecursionlinked-listsingly-linked-list
AKASH AJITH
AKASH AJITH

Reputation: 11

Remove nodes from linked list leetcode , time limit exceeded error

You are given the head of a linked list.

Remove every node which has a node with a strictly greater value anywhere to the right side of it.

Return the head of the modified linked list.

I have tried the method of recursion using the following code but nevertheless time limit exceeded is what I get

class Solution {
public:
    ListNode* solve(ListNode* head)
    {
        ListNode* temp;
        if(head->next=NULL)
            return head;
        if(head->next->val>head->val)
        {
            head=head->next;
        }
        for(temp=head;temp->next!=NULL;temp=temp->next)
        {
            while(temp->next->next!=NULL)
            {
                if(temp->next->val<temp->next->next->val)
                temp->next=temp->next->next;
            }
        }
        solve(head);
        return head;
    }
    ListNode* removeNodes(ListNode* head) {
        
        return solve(head);
    
    }
};

Upvotes: 1

Views: 168

Answers (1)

ggorlen
ggorlen

Reputation: 57175

Leetcode gives a limit of n = 10**5 on this problem, so if you have a nested loop over n, that's 10_000_000_000 iterations. That's a clear TLE before any code is written.

Recursion is generally not a great tool for linked list problems in imperative languages: it's harder to access the previous node and it's easy to blow the stack. Linked lists have linear rather than logarithmic depth like balanced trees. If you use recursion here, you need a stack size of 10**5.

The problem is asking us to remove any node where there is another node with a greater value later in the list. To achieve this linearly (practically speaking, that means making one to three passes over the list), we could reformulate the problem to loosen its requirements.

A simpler problem is to remove any node with a value strictly greater to the left of it. Now, the linear algorithm is more apparent: walk the list, keeping track of the largest value seen so far, and determine removals for nodes based on that information.

For each node in the iteration:

  • If its value is less than the greatest seen so far, remove it.
  • If its value is equal to or greater than the greatest seen so far, keep it in the list and set its value as the new greatest.

Applying this strategy to the main problem, we could reverse the list, run the above algorithm, then reverse the list again and return the head. This is a three-pass linear solution with constant space.

Other approaches are possible. As is commonly the case, you can trade space for time to use fewer passes.

Upvotes: 1

Related Questions