add a solution for 143

fishercoder1534 · fishercoder1534 · commit 599429f97351 · 2021-10-25T16:12:43.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_143.java b/src/main/java/com/fishercoder/solutions/_143.java
@@ -51,4 +51,43 @@ public void reorderList(ListNode head) {
             }
         }
     }
+
+    public static class Solution2 {
+        /**
+         * My completely original solution on 10/25/2021, although not super efficient in time complexity,
+         * since I keep going through the rest of the list to the end at each iteration, it's accepted on LeetCode.
+         */
+        public void reorderList(ListNode head) {
+            int len = getLen(head);
+            if (len <= 2) {
+                return;
+            }
+            ListNode curr = head;
+            for (int i = 0; i < len / 2; i++) {
+                ListNode tmp = curr;
+                ListNode newHead = curr.next;
+                while (tmp.next.next != null) {
+                    tmp = tmp.next;
+                }
+                if (tmp == curr) {
+                    break;
+                }
+                ListNode tail = tmp.next;
+                tmp.next = null;
+                curr.next = tail;
+                tail.next = newHead;
+                curr = newHead;
+            }
+        }
+
+        private int getLen(ListNode head) {
+            int len = 0;
+            ListNode tmp = head;
+            while (tmp != null) {
+                tmp = tmp.next;
+                len++;
+            }
+            return len;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_143Test.java b/src/test/java/com/fishercoder/_143Test.java
@@ -0,0 +1,41 @@
+package com.fishercoder;
+
+import com.fishercoder.common.classes.ListNode;
+import com.fishercoder.common.utils.LinkedListUtils;
+import com.fishercoder.solutions._143;
+import com.fishercoder.solutions._1862;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import java.util.Arrays;
+
+import static org.junit.Assert.assertEquals;
+
+public class _143Test {
+    private static _143.Solution1 solution1;
+    private static _143.Solution2 solution2;
+    private static ListNode head;
+    private static ListNode expected;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _143.Solution1();
+        solution2 = new _143.Solution2();
+    }
+
+    @Test
+    public void test1() {
+        head = LinkedListUtils.createSinglyLinkedList(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
+        expected = LinkedListUtils.createSinglyLinkedList(Arrays.asList(1, 7, 2, 6, 3, 5, 4));
+        solution1.reorderList(head);
+        assertEquals(expected, head);
+    }
+
+    @Test
+    public void test2() {
+        head = LinkedListUtils.createSinglyLinkedList(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
+        expected = LinkedListUtils.createSinglyLinkedList(Arrays.asList(1, 7, 2, 6, 3, 5, 4));
+        solution2.reorderList(head);
+        assertEquals(expected, head);
+    }
+}
