Used a hashtable to make it double link list then TLE, T^T, Why?


  • 1
    Y

    It should be roughly an insertion complexity - O(n^2)

    but TLE, why?

    Is the hashtable hacking the complexity?

    Or is that my code is not neat enough?

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *	 int val;
     *	 ListNode *next;
     *	 ListNode(int x) : val(x), next(NULL) {}
     * };
     */
     #include <unordered_map>
    
    class Solution {
    public:
    	//typedef 
    	typedef ListNode* iterator; 
    
    	ListNode* insertionSortList(ListNode* head) {
    		// IMPORTANT: Please reset any member data you declared, as
    		// the same Solution instance will be reused for each test case.
    		if( head == NULL || head -> next == NULL ){
    			return head;
    		}
    		iterator fp = head->next;
    		iterator sp = head;
    		
    		unordered_map<iterator, iterator> ht; 
    
    		ht[head->next] = head;
    		while( fp != NULL ){
    			iterator tmp = sp;
    			while( tmp->val > fp->val ){
    				if( ht.find(tmp) == ht.end() ){
    					break;
    				}else{
    					tmp = ht[tmp];
    				}
    			}
    			if( tmp->val > fp->val ){
    				sp->next = fp->next;
    				fp->next = head;
    				head = fp;
    			}else{
    				if( tmp->next = fp ){
    
    				}else{
    					sp->next = fp->next;
    					fp->next = tmp->next;
    					tmp->next = fp;
    				}
    			}
    			sp = fp;
    			fp = fp->next;
    		}
    
    		return head; 
    	}
    };

  • 0
    S

    Maybe you just modify the list with wrong next pointer of some nodes. When judge parse your returning head, it lead to endless loop.


  • 0
    Y

    Too much overhead, the loop is good in general. But the hashtable is not necessary.


Log in to reply
 

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