add a solution for 92

fishercoder1534 · fishercoder1534 · commit c39f7d2e327e · 2021-10-25T20:17:23.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_92.java b/src/main/java/com/fishercoder/solutions/_92.java
@@ -33,8 +33,39 @@ public ListNode reverseBetween(ListNode head, int m, int n) {
                 pre.next = then;
                 then = start.next;
             }
-
             return dummy.next;
         }
     }
+
+    public static class Solution2 {
+        /**
+         * My completely original solution on 10/25/2021.
+         */
+        public ListNode reverseBetween(ListNode head, int left, int right) {
+            ListNode pre = new ListNode(-1);
+            pre.next = head;
+            ListNode tmp = pre;
+            right -= left;
+            while (left-- > 1 && tmp != null) {
+                tmp = tmp.next;
+            }
+            ListNode intersection = tmp;
+            ListNode reverseHead = tmp.next;
+            ListNode prev = null;
+            right++;
+            int original = right;
+            while (right-- > 0 && reverseHead != null) {
+                ListNode next = reverseHead.next;
+                reverseHead.next = prev;
+                prev = reverseHead;
+                reverseHead = next;
+            }
+            intersection.next = prev;
+            while (original-- > 0) {
+                intersection = intersection.next;
+            }
+            intersection.next = reverseHead;
+            return pre.next;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_92Test.java b/src/test/java/com/fishercoder/_92Test.java
@@ -12,19 +12,24 @@
 
 public class _92Test {
     private static _92.Solution1 solution1;
+    private static _92.Solution2 solution2;
     private static ListNode head;
     private static ListNode expected;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _92.Solution1();
+        solution2 = new _92.Solution2();
     }
 
     @Test
     public void test1() {
         head = LinkedListUtils.createSinglyLinkedList(Arrays.asList(1, 2, 3, 4, 5));
         expected = LinkedListUtils.createSinglyLinkedList(Arrays.asList(1, 4, 3, 2, 5));
         assertEquals(expected, solution1.reverseBetween(head, 2, 4));
+
+        head = LinkedListUtils.createSinglyLinkedList(Arrays.asList(1, 2, 3, 4, 5));
+        assertEquals(expected, solution2.reverseBetween(head, 2, 4));
     }
 
 }
