C# solution with a SortedDictionary


  • 0
    M
    public class Solution {
        public ListNode MergeKLists(ListNode[] lists) 
        {
            if (lists == null)
            {
                return null;
            }
            
            var heads = new SortedDictionary<int, List<ListNode>>();
            ListNode result = null;
            ListNode currPos = null;
            foreach (var list in lists)
            {
                if (list != null)
                {
                    AddToHeads(list, heads);
                }
            }
            
            if (heads.Count != 0)
            {
                result = GetListWithMinHeadVal(heads);
                currPos = result;
                AddToHeads(result.next, heads);
            }
            else
            {
                return result;
            }
            
            while (heads.Count > 0)
            {
                ListNode currMin = GetListWithMinHeadVal(heads);
                AddToHeads(currMin.next, heads);
                currPos.next = currMin;
                currPos = currMin;
            }
            
            return result;
        }
        
        public static ListNode GetListWithMinHeadVal(SortedDictionary<int, List<ListNode>> heads)
        {
            int minKey = heads.Keys.First();
            List<ListNode> listsWithSmallestVals = heads[minKey];
            
            ListNode minList = listsWithSmallestVals[0];
            listsWithSmallestVals.RemoveAt(0);
            
            if (listsWithSmallestVals.Count == 0)
            {
                heads.Remove(minKey);
            }
            
            return minList;
        }
        
        public static void AddToHeads(ListNode list, SortedDictionary<int, List<ListNode>> heads)
        {
            if (list == null)
            {
                return;
            }
            
            List<ListNode> storedList;
            if (heads.TryGetValue(list.val, out storedList))
            {
                storedList.Add(list);
            }
            else
            {
                heads.Add(list.val, new List<ListNode>() { list });
            }
        }
    }

Log in to reply
 

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