07/29 linkedList problems

surajr · surajr · commit d56cf6a5f033 · 2018-07-29T09:39:44.000-05:00
diff --git a/java/mergeKLists.java b/java/mergeKLists.java
@@ -1,28 +1,33 @@
 //Divide and Conquer method
 
-public class Solution {
+class Solution {
     public ListNode mergeKLists(ListNode[] lists) {
-        if (lists == null || lists.length == 0) return null;
-        return sort(lists, 0, lists.length - 1);
+        return merge(lists, 0, lists.length-1);
     }
-    
-    private ListNode sort(ListNode[] lists, int lo, int hi) {
-        if (lo >= hi) return lists[lo];
-        int mid = lo + (hi - lo) / 2;
-        ListNode l1 = sort(lists, lo, mid);
-        ListNode l2 = sort(lists, mid + 1, hi);
-        return merge(l1, l2);
+
+    public ListNode merge(ListNode[] lists, int start, int end){
+        if(start == end) return lists[start];
+        else if(start < end){
+            int mid = start + (end-start)/2;
+            ListNode left = merge(lists, start, mid);
+            ListNode right = merge(lists, mid+1, end);
+            return mergeLists(left, right);
+        }
+        else
+            return null;
     }
-    
-    private ListNode merge(ListNode l1, ListNode l2) {
-        if (l1 == null) return l2;
-        if (l2 == null) return l1;
-        if (l1.val < l2.val) {
-            l1.next = merge(l1.next, l2);
+
+    public ListNode mergeLists(ListNode l1, ListNode l2){
+        if(l1 == null) return l2;
+        else if(l2 == null) return l1;
+        else if(l1.val < l2.val){
+            l1.next = mergeLists(l1.next, l2);
             return l1;
         }
-        l2.next = merge(l1, l2.next);
-        return l2;
+        else {
+            l2.next = mergeLists(l1, l2.next);
+            return l2;
+        }
     }
 }
 
@@ -38,34 +43,34 @@ private ListNode merge(ListNode l1, ListNode l2) {
  */
 class Solution {
     public ListNode mergeKLists(ListNode[] lists) {
-        
+
         ListNode dummy = new ListNode(0), cur = dummy;
-        
+
         if(lists.length == 0)
             return null;
-        
+
         PriorityQueue<ListNode> minHeap = new PriorityQueue<>(lists.length, new Comparator<ListNode>(){
             public int compare(ListNode l1, ListNode l2)
             {
                 return l1.val - l2.val;
             }
         });
-        
+
         for(ListNode list : lists)
             if(list != null)
                 minHeap.offer(list);
-        
+
         while(!minHeap.isEmpty())
         {
             ListNode temp = minHeap.poll();
             cur.next = temp;
             if(temp.next != null)
-                minHeap.offer(temp.next);      
-            
+                minHeap.offer(temp.next);
+
             cur = temp;
         }
-        
-        return dummy.next;        
-        
+
+        return dummy.next;
+
     }
 }
diff --git a/java/mergeTwoLists.java b/java/mergeTwoLists.java
@@ -10,7 +10,7 @@ public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
         ListNode p1 = l1, p2 = l2;
         ListNode result = new ListNode(-1);
         ListNode p3 = result;
-        
+
         while(p1 != null || p2 != null)
         {
             if(p1 == null && p2 != null)
@@ -29,16 +29,42 @@ else if(p1 != null && p2 == null)
                 {
                     p3.next = new ListNode(p1.val);
                     p1 = p1.next;
-                }                    
+                }
                 else
                 {
                     p3.next = new ListNode(p2.val);
                     p2 = p2.next;
-                }               
+                }
             }
-            p3 = p3.next;      
-           
+            p3 = p3.next;
+
         }
         return result.next;
     }
 }
+
+
+
+
+
+
+
+/* better way to solve this */
+
+
+
+class Solution {
+    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
+        if(l1 == null) return l2;
+        if(l2 == null) return l1;
+        if(l1.val < l2.val){
+            l1.next = mergeTwoLists(l1.next, l2);
+            return l1;
+        }
+        else{
+            l2.next = mergeTwoLists(l1, l2.next);
+            return l2;
+        }
+
+    }
+}
diff --git a/java/swapPairs.java b/java/swapPairs.java
@@ -6,21 +6,20 @@
  *     ListNode(int x) { val = x; }
  * }
  */
-class Solution {
-    public ListNode swapPairs(ListNode head) {
-        ListNode first = new ListNode(-1);
-        first.next = head;
-        
-        ListNode pre = first, cur = head;
-        
-        while(cur != null && cur.next != null)
-        {
-            pre.next = cur.next;
-            pre = cur;
-            cur = cur.next.next;
-            pre.next.next = pre;
-        }
-        pre.next = cur;
-        return first.next;
-    }
-}
+ class Solution {
+     public ListNode swapPairs(ListNode head) {
+         ListNode dummy = new ListNode(-1);
+         dummy.next = head;
+         ListNode cur = dummy;
+
+         while(cur.next != null && cur.next.next != null){
+             ListNode first = cur.next;
+             ListNode second = cur.next.next;
+             first.next = second.next;
+             second.next = cur.next;
+             cur.next = second;
+             cur = cur.next.next;
+         }
+         return dummy.next;
+     }
+ }
