add a solution for 25

fishercoder1534 · fishercoder1534 · commit 7462d41fa46b · 2021-10-25T17:22:41.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_25.java b/src/main/java/com/fishercoder/solutions/_25.java
@@ -84,4 +84,57 @@ public ListNode reverseKGroup(ListNode head, int k) {
         }
     }
 
+    public static class Solution3 {
+        /**
+         * My completely original solution on 10/25/2021. Beats 100% submissions on LeetCode in runtime.
+         * Again, using a pen and paper to visualize the process helps a lot!
+         * My helper function returns two nodes: reversed node head and the starting node for the next reversal.
+         */
+        public ListNode reverseKGroup(ListNode head, int k) {
+            ListNode pre = new ListNode(-1);
+            pre.next = head;
+            ListNode tmp = pre;
+            ListNode curr = head;
+            ListNode[] result = new ListNode[]{null, curr};
+            do {
+                result = reverseKGroupHelper(result[1], k);
+                if (result[0] == result[1]) {
+                    tmp.next = result[0];
+                    return pre.next;
+                } else {
+                    tmp.next = result[0];
+                    while (tmp.next != null) {
+                        tmp = tmp.next;
+                    }
+                }
+            } while (true);
+        }
+
+        private ListNode[] reverseKGroupHelper(ListNode head, int k) {
+            int originalK = k;
+            ListNode tmp = head;
+            while (tmp != null) {
+                tmp = tmp.next;
+                k--;
+            }
+            if (k > 0) {
+                return new ListNode[]{head, head};
+            } else {
+                tmp = head;
+                k = originalK;
+                ListNode prev = null;
+                while (tmp != null) {
+                    ListNode next = tmp.next;
+                    tmp.next = prev;
+                    prev = tmp;
+                    tmp = next;
+                    k--;
+                    if (k == 0) {
+                        return new ListNode[]{prev, tmp};
+                    }
+                }
+                return null;
+            }
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_25Test.java b/src/test/java/com/fishercoder/_25Test.java
@@ -9,31 +9,39 @@
 import static org.junit.Assert.assertEquals;
 
 public class _25Test {
-    private static _25.Solution1 test;
-    private static _25.Solution2 test2;
-    private static ListNode actual;
+    private static _25.Solution1 solution1;
+    private static _25.Solution2 solution2;
+    private static _25.Solution3 solution3;
     private static ListNode expected;
     private static ListNode head;
+    private static int k;
 
     @BeforeClass
     public static void setup() {
-        test = new _25.Solution1();
-        test2 = new _25.Solution2();
+        solution1 = new _25.Solution1();
+        solution2 = new _25.Solution2();
+        solution3 = new _25.Solution3();
     }
 
     @Test
     public void test1() {
         head = LinkedListUtils.contructLinkedList(new int[]{1, 2, 3, 4, 5});
-        actual = test.reverseKGroup(head, 2);
+        k = 2;
         expected = LinkedListUtils.contructLinkedList(new int[]{2, 1, 4, 3, 5});
-        assertEquals(actual, expected);
+        assertEquals(expected, solution1.reverseKGroup(head, k));
     }
 
     @Test
     public void test2() {
         head = LinkedListUtils.contructLinkedList(new int[]{1, 2, 3, 4, 5, 6, 7});
-        actual = test2.reverseKGroup(head, 4);
         expected = LinkedListUtils.contructLinkedList(new int[]{4, 3, 2, 1, 5, 6, 7});
-        assertEquals(actual, expected);
+        assertEquals(expected, solution2.reverseKGroup(head, 4));
+    }
+
+    @Test
+    public void test3() {
+        head = LinkedListUtils.contructLinkedList(new int[]{1, 2, 3, 4, 5, 6, 7});
+        expected = LinkedListUtils.contructLinkedList(new int[]{4, 3, 2, 1, 5, 6, 7});
+        assertEquals(expected, solution3.reverseKGroup(head, 4));
     }
 }
