My accepted solution.. took 20ms.. can we make it better?


  • 0
    H
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *rotateRight(ListNode *head, int k) {
        ListNode *current = head;
        int count = 0;
        // create a map
        map<int ,  ListNode*> mymap;
        
        if(current == NULL)
            return current;
        
        while(current != NULL){
     //       count = 0;
            mymap.insert(pair<int ,  ListNode*>(count , current));
            count++;
            current = current->next;
        }
        cout << "Length of list " << count << endl;
        // count is the length of the list
        if(k == count)
            return head;
            // this check is because when K is very large it will round off
        if(k > count)
            k %= count;
            
        map<int ,  ListNode *> :: iterator prev = mymap.find(count-k-1);
        map<int ,  ListNode *> :: iterator last = mymap.find(count-1);
    
        last->second->next = head;
        head = prev->second->next;
        prev->second->next = NULL;
        
        return head;
    
            
        }
    };
    

    I used hashtable to solve this.. O(n).. Can we solve better? Please suggest
    We can also solve this w/0 hash table.. just iterate and count the number of nodes.
    Store the last node pointer and iterate again to reach node (count-k+1) from start.. after that follow the same logic I used. it will take O(2n) = O(n)


Log in to reply
 

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