add iterative solution for 21

fishercoder1534 · fishercoder1534 · commit 69af0137c2e7 · 2020-01-17T07:26:27.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_21.java b/src/main/java/com/fishercoder/solutions/_21.java
@@ -38,4 +38,30 @@ public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
         }
     }
 
+    public static class Solution2 {
+        /**
+         * iterative solution
+         * Time: O(m+n)
+         * Space: O(1)
+         */
+        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
+            ListNode pre = new ListNode(-1);
+            ListNode curr = pre;
+
+            while (l1 != null && l2 != null) {
+                if (l1.val < l2.val) {
+                    curr.next = l1;
+                    l1 = l1.next;
+                } else {
+                    curr.next = l2;
+                    l2 = l2.next;
+                }
+                curr = curr.next;
+            }
+
+            curr.next = l1 == null ? l2 : l1;
+            return pre.next;
+        }
+    }
+
 }
diff --git a/src/test/java/com/fishercoder/_21Test.java b/src/test/java/com/fishercoder/_21Test.java
@@ -11,12 +11,14 @@
 
 public class _21Test {
     private static _21.Solution1 solution1;
+    private static _21.Solution2 solution2;
     private static ListNode l1;
     private static ListNode l2;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _21.Solution1();
+        solution2 = new _21.Solution2();
     }
 
     @Test
@@ -26,4 +28,11 @@ public void test1() {
         assertEquals(ListNode.createSinglyLinkedList(Arrays.asList(1, 2, 3, 4, 5)), solution1.mergeTwoLists(l1, l2));
     }
 
+    @Test
+    public void test2() {
+        l1 = ListNode.createSinglyLinkedList(Arrays.asList(1, 3, 5));
+        l2 = ListNode.createSinglyLinkedList(Arrays.asList(2, 4));
+        assertEquals(ListNode.createSinglyLinkedList(Arrays.asList(1, 2, 3, 4, 5)), solution2.mergeTwoLists(l1, l2));
+    }
+
 }
