leetcode

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

insertion-sort-list.dart (1808B)

      1 //Given a linked list sort it then return the sorted linked list.
      2 //You are supposed to use insertion sort, but that would be slow
      3 //so I used merge sort. To do this I first placed all values in an array
      4 //then sent those values to a merge sort function which runs merge sort on them.
      5 //From there that list is sent to the toLinkedList function
      6 //which takes an input of type list and returns it as a linked list.
      7 //Time: 286ms Beats: 75%
      8 //Memory: 150.3MB Beats: 25%
      9 
     10 class Solution {
     11   ListNode? insertionSortList(ListNode? head) {
     12       List<int> vals = [];
     13       while(head != null){
     14           vals.add(head.val);
     15           head = head.next;
     16       }
     17       vals = merge_sort(vals);
     18       return toLinkedList(vals);
     19   }
     20   List<int> merge_sort(List<int> vals){
     21     if(vals.length == 1){
     22       return vals;
     23     }
     24     List<int> l1 = merge_sort(vals.sublist(0, (vals.length/2).toInt()));
     25     List<int> l2 = merge_sort(vals.sublist((vals.length/2).toInt()));
     26     List<int> l3 = [];
     27     int l1_pt = 0;
     28     int l2_pt = 0;
     29     while(l1_pt < l1.length && l2_pt < l2.length){
     30       if(l1[l1_pt] < l2[l2_pt]){
     31         l3.add(l1[l1_pt]);
     32         l1_pt += 1;
     33       }
     34       else{
     35         l3.add(l2[l2_pt]);
     36         l2_pt += 1;
     37       }
     38     }
     39     while(l1_pt < l1.length){
     40       l3.add(l1[l1_pt]);
     41       l1_pt += 1;
     42     }
     43     while(l2_pt < l2.length){
     44       l3.add(l2[l2_pt]);
     45       l2_pt += 1;
     46     }
     47     return l3;
     48   }
     49   ListNode? toLinkedList(List<int> vals){
     50     if(vals.length == 0){
     51       return null;
     52     }
     53     if(vals.length == 1){
     54       return new ListNode(vals[0]);
     55     }
     56     ListNode last = new ListNode(vals[0]);
     57     ListNode first = last;
     58     for(int i = 1 ; i < vals.length ; ++i){
     59       ListNode current = new ListNode(vals[i]);
     60       last.next = current;
     61       last = current;
     62     }
     63     return first;
     64   }
     65 }