leetcode

commit 0ee99efcbae18af28bb859be05326ffd816243ae
parent c4675f449b064c100b1ea5ecc93496e7a79e1008
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Tue, 18 Apr 2023 17:13:39 -0500

Optimized solution to merge sorted lists without further sorting

Diffstat:
A
merge-two-sorted-lists/merge-two-sorted-listsV2.dart
 | 
81
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 81 insertions(+), 0 deletions(-)
diff --git a/merge-two-sorted-lists/merge-two-sorted-listsV2.dart b/merge-two-sorted-lists/merge-two-sorted-listsV2.dart
@@ -0,0 +1,81 @@
+//Made list only add if the value in one of the lists is larger than the other
+//this made it so that I did not have to run an O(nlog(n)) sort after the list is
+//fully setup.
+
+//Time: 253ms Beats: 95.56%
+//Memory 144MB Beats: 40.47%
+
+class ListNode{
+    int val = 0;
+    ListNode? next;
+}
+
+void main(){
+    Solution sol = new Solution();
+    ListNode head1 = new ListNode();
+    ListNode ln1 = new ListNode();
+    head1.val = 4;
+    ln1.val = 5;
+    head1.next = ln1;
+    ListNode ln2 = new ListNode();
+    ln2.val = 10;
+    ln1.next = ln2;
+    ListNode? ln = sol.mergeTwoLists(head1, ln1);
+    while(ln?.val != null){
+        print(ln?.val);
+        ln = ln?.next;
+    }
+}
+class Solution {
+  ListNode? mergeTwoLists(ListNode? list1, ListNode? list2) {
+      
+    if(list1?.val == null && list2?.val == null){
+      return list1 ;
+    }
+
+    List<int?> vals = [];
+
+    while(list1?.val != null && list2?.val != null){
+      int? v1 = list1?.val;
+      int? v2 = list2?.val;
+      if((v1 ?? 0) > (v2 ?? 0)){
+        vals.add(v2);
+        list2 = list2?.next;
+      }
+      else{
+        vals.add(v1);
+        list1 = list1?.next;
+      }
+
+
+
+
+    }
+    while(list1?.val != null){
+      vals.add(list1?.val);
+      list1 = list1?.next;
+
+    }
+    while(list2?.val != null){
+      vals.add(list2?.val);
+      list2 = list2?.next;
+
+    }
+    
+    ListNode ln = new ListNode();
+    ListNode ln1 = new ListNode();
+    ListNode start = ln;
+    for(int i = 0 ; i < vals.length - 1; ++i){
+      ln.val = vals[i] ?? 0;
+      ln.next = ln1;
+      ln = ln1;
+      ln1 = new ListNode();
+    }
+      ln.val = vals[vals.length - 1] ?? 0;
+      return start;
+  }
+
+
+
+
+}