Priority Queue based solution


  • 0
    P
    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            
            PriorityQueue pq(&lists);
        	if(pq.Build())
        	{
        		List l;
        		int val;
        		bool first = true;
        		bool keepOn = true;
        		
        		while(keepOn)
        		{
        		    keepOn = pq.GetMin(val);
        			PushBack(l, val);
        			if(first)
        			{
        				first = false;
        				l.head = l.tail;
        			}
        		}
        		
        		return l.head;
        	}
        	else
        		return NULL;
        }
        
        struct List
        {
        	ListNode * head;
        	ListNode * tail;
        	List() : head(NULL), tail(NULL){}
        };
        
        void PushBack(List& l, int val)
        {
        	ListNode * ntail = new ListNode(val);
        	if(l.tail)
        		l.tail->next = ntail;
        	l.tail = ntail;
        }
        
        struct PriorityQueue{
    
        	PriorityQueue(vector<ListNode*>* v) : m_Container(v), m_NumLists(v->size())
        		{
        		}
        
        	int Parent(int i){ assert(i>0); return ((i+1)/2 - 1);}
        	int Left(int i){ return (2*(i+1)-1);}
        	int Right(int i){ return (2*(i+1));}
        
        	void MinHeapify(int i)
        		{
        			int l = Left(i);
        			int r = Right(i);
        			int minIdx;
        
        			if(l < m_NumLists && (*m_Container)[l] && (*m_Container)[l]->val < (*m_Container)[i]->val)
        				minIdx = l;
        			else
        				minIdx = i;
        
        			if(r < m_NumLists && (*m_Container)[r] && (*m_Container)[r]->val < (*m_Container)[minIdx]->val)
        				minIdx = r;
        
        			if(minIdx != i)
        			{
        				ListNode * tmp = (*m_Container)[i];
        				(*m_Container)[i] = (*m_Container)[minIdx];
        				(*m_Container)[minIdx] = tmp;
        				MinHeapify(minIdx);
        			}
        		}
        
        	bool Build()
        		{
        			auto cit = remove_if(m_Container->begin(), m_Container->end(),
        								 [](ListNode * tmp)->bool{
        									 return tmp == NULL;
        				});
        
        			m_Container->erase(cit, m_Container->end());
        			m_NumLists = m_Container->size();
        
        			if(m_Container->size() > 0)
        			{
        				for(int i = m_Container->size()/2; i>=0; i--)
        					MinHeapify(i);
        				return true;
        			}
        			else
        				return false;
        		}
        
        	bool GetMin(int& val)
        		{
        			val = (*m_Container)[0]->val;
        
        			ListNode * tmp = (*m_Container)[0]->next;
        			delete (*m_Container)[0];
        			(*m_Container)[0] = tmp;
        
        			if(tmp)
        			{
        				MinHeapify(0);
        				return true;
        			}
        			else
        			{
        				if(m_NumLists > 1)
        				{
        					swap((*m_Container)[0], (*m_Container)[m_NumLists-1]);
        					m_NumLists--;
        					MinHeapify(0);
        					return true;
        				}
        				else
        					return false;
        			}
        		}
        
        	vector<ListNode *>* m_Container;
        	int m_NumLists;
        };
        
    };

Log in to reply
 

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