Why using hashmap is slower than just using traverse?


  • 0
    N

    This the code of using hashmap to directly locate the element before the should-deleting element. The ideal is simple that using the space complexity reduces the time complexity. But this code takes 8 ms to finish which is longer than the time of following traverse linked list one.

    /**
         * Definition for singly-linked list.
         * struct ListNode {
         *     int val;
         *     ListNode *next;
         *     ListNode(int x) : val(x), next(NULL) {}
         * };
         */
    class Solution {
    public:
        ListNode* removeNthFromEnd(ListNode* head, int n) {
            unordered_map<int, ListNode*> myMap;
            ListNode * List = head;
            int count=0;
            while(List!=NULL)
            {
                myMap[count]=List;
                List = List->next;
                count++;
            }
            
            if(count-n-1<0)
            {
                head = head->next;
                return head;
            }
            
            myMap[count-n-1]->next = myMap[count-n]->next;
            return head;
            
        }
    };
    
    
    class Solution {
    public:
        ListNode* removeNthFromEnd(ListNode* head, int n) {
            int count=0;
            ListNode *List=head;
            while(List!=NULL)
            {
                List = List->next;
                count++;
            }
            
            if(count-n-1<0)
            {
                head = head->next;
                return head;
            }
            
            List=head;
            for(int i=0;i<count-n-1;i++)
            {
                List = List->next;
            }
               
            
            List->next = List->next->next;
            return head;
            
        }
    };
    

    I am wondering how this happens. It seems that if you use some classes from library, you get punishment. Is that the methods from classes are always slower, so when you optimize your code, try not to use libraries?

    Anyone could help me out?

    Thanks


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.