GO 16ms O(nlogk) Q based beat 97%


  • 0
    D

    Very similar to what I implemented with cpp before.

    // Merge K lists
    func mergeKLists(lists []*ListNode) *ListNode {
    	if len(lists) == 0 {
    		return nil
    	}
    
    	q := NewQueue(lists)
    	for q.Length() > 1 {
    		q.Push(mergeTwoLists(q.Pop(), q.Pop()))
    	}
    
    	return q.Pop()
    }
    
    // You don't need to read on.
    
    // Queue implementation
    type Queue interface {
    	Length() int
    	Push(node *ListNode)
    	Pop() *ListNode
    }
    
    type que struct {
    	elements []*ListNode
    }
    
    func NewQueue(lists []*ListNode) Queue {
    	if lists == nil {
    		lists = make([]*ListNode, 0)
    	}
    
    	return &que{
    		elements: lists,
    	}
    }
    
    func (q *que) Length() int {
    	return len(q.elements)
    }
    
    func (q *que) Push(node *ListNode) {
    	q.elements = append(q.elements, node)
    }
    
    func (q *que) Pop() *ListNode {
    	len := len(q.elements)
    	if len == 0 {
    		panic("queue is empty.")
    	}
    	n := q.elements[0]
    	q.elements = q.elements[1:]
    	return n
    }
    
    // Merge 2 lists
    func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    	if l1 == nil {
    		return l2
    	}
    
    	if l2 == nil {
    		return l1
    	}
    
    	head := ListNode{}
    	prev := &head
    
    	for l1 != nil && l2 != nil {
    		if l1.Val < l2.Val {
    			prev.Next = l1
    			l1 = l1.Next
    		} else {
    			prev.Next = l2
    			l2 = l2.Next
    		}
    		prev = prev.Next
    	}
    
    	if l1 != nil {
    		prev.Next = l1
    	}
    
    	if l2 != nil {
    		prev.Next = l2
    	}
    
    	return head.Next
    }
    

Log in to reply
 

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