leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

merge-k-sorted-lists.dart (2418B)

      1 //This is a leetcode hard problem where you need to merge K sorted lists together.
      2 //To do this I first changed the linked lists to arrays. I then went through each array
      3 //and merged them to one array that was sorted. From there I then merged them together into
      4 //a singly linked list. The time complexity of this is O(nlog(n)) where n is the number of total items in all
      5 //of the lists. This is because the sorting algorithm bumps it up from O(n).
      6 //To optimize this I really should have just iterated through the linked lists pulling out
      7 //the values that were the lowest into a new list and then returned that. This would still be an O(nlog(n))
      8 //algorithm but would execute much faster due to decreased overhead.
      9 //Runtime:682ms Beats:16.92%
     10 //Memory: 147.3MB Beats: 75.38%
     11 
     12 
     13 
     14 /**
     15  * Definition for singly-linked list.
     16  * class ListNode {
     17  *   int val;
     18  *   ListNode? next;
     19  *   ListNode([this.val = 0, this.next]);
     20  * }
     21  */
     22 class Solution {
     23   ListNode? mergeKLists(List<ListNode?> lists) {
     24 
     25     List<List<int>> sort_list = [];
     26     for(int i = 0 ; i < lists.length; ++i){
     27       sort_list.add(<int>[]);
     28     }
     29     int count = 1;
     30     for(int i = 0 ; i < lists.length ; ++i){
     31         while(true){
     32             if(lists[i] == null){
     33                 break;
     34             }
     35             sort_list[i].add(lists[i]?.val ?? 0);
     36             lists[i] = lists[i]?.next;
     37             count += 1;
     38         }
     39     }
     40     List<int> sorted_vals = [];
     41     int lowest_num = 0;
     42     int index = 0;
     43     int first_list = 0;
     44     for(int i = 0 ; i < count + 1 ; ++i){
     45       try{
     46         lowest_num = sort_list[first_list][0];
     47       }
     48       catch(exception){
     49         first_list += 1;
     50         i -= 1;
     51         continue;
     52       }
     53       index = first_list;
     54       for(int x = 1 ; x < lists.length; ++x){
     55         if(sort_list[x].isEmpty){
     56           continue;
     57         }
     58          int current = sort_list[x][0];
     59          if(current < lowest_num){
     60            lowest_num = current;
     61            index = x;
     62          }
     63       }
     64       sort_list[index].removeAt(0);
     65       sorted_vals.add(lowest_num);
     66     }
     67     if(sorted_vals.length == 0){
     68       return null;
     69     }
     70     ListNode head = new ListNode();
     71     head.val = sorted_vals[0];
     72     ListNode itr = head;
     73     ListNode next;
     74     for(int i = 1 ; i < sorted_vals.length; ++i){
     75         next = new ListNode();
     76         next.val = sorted_vals[i];
     77         itr.next = next;
     78         itr = next;
     79     }
     80 
     81     return head;
     82   }
     83 }