Straightforward Linked List Solution C++


  • 0

    It is O(nk), but easy to come up with the idea at the beginning.

    class Solution {
    public:
        struct ListNode{
            int val;
            ListNode *next;
            ListNode(int x):val(x),next(NULL){}
        };
    
        vector<double> medianSlidingWindow(vector<int>& nums, int k) {
            vector<double> res;
            ListNode * head = NULL;
    
            for(int i = 0; i < k; i++)
                head = insertNode(head, nums[i]);
            res.push_back(getMedian(head, k));
    
            for(int i = k; i < nums.size(); i++){
                head = deleteNode(head, nums[i-k]);
                head = insertNode(head, nums[i]);
                res.push_back(getMedian(head, k));
            }
    
            return res;
        }
    
        ListNode* insertNode(ListNode *head, int x){
             if(!head || x <= head->val){
                ListNode *node = new ListNode(x);
                node->next = head;
                return node;
            }
    
            ListNode* node = head;
            while(node->next && x > node->next->val) node = node->next;
            ListNode *temp = node->next;
            node->next = new ListNode(x);
            node->next->next = temp;
            return head;
        }
    
        ListNode* deleteNode(ListNode *head, int x){
            if(x == head->val)
                return head->next;
    
            ListNode* node = head;
            while(node->next && node->next->val != x) node = node->next;
            node->next = node->next->next;
            return head;
        }
    
        double getMedian(ListNode *head, int k){
            int step = (k-1) / 2;
            ListNode *node = head;
            while(step--)
                node = node->next;
    
            if(k % 2) return node->val;
            return node->val / 2.0 + node->next->val / 2.0; // In case of overflow
        }
    };
    

Log in to reply
 

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