refactor 92

fishercoder1534 · fishercoder1534 · commit e8f7f3fd5508 · 2018-03-03T07:54:29.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_92.java b/src/main/java/com/fishercoder/solutions/_92.java
@@ -1,123 +1,49 @@
 package com.fishercoder.solutions;
 
 import com.fishercoder.common.classes.ListNode;
-import com.fishercoder.common.utils.CommonUtils;
 
-/**Reverse a linked list from position m to n. Do it in-place and in one-pass.
-
- For example:
- Given 1->2->3->4->5->NULL, m = 2 and n = 4,
-
- return 1->4->3->2->5->NULL.
-
- Note:
- Given m, n satisfy the following condition:
- 1 ≤ m ≤ n ≤ length of list.*/
+/**
+ * 92. Reverse Linked List II
+ *
+ * Reverse a linked list from position m to n. Do it in-place and in one-pass.
+ *
+ * For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4,
+ *
+ * return 1->4->3->2->5->NULL.
+ *
+ * Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.
+ */
 public class _92 {
 
-    // then I turned to Discuss and find this most upvoted solution:
-    // https://discuss.leetcode.com/topic/8976/simple-java-solution-with-clear-explanation, it's
-    // indeed concise, I knew there's such a solution there
-    public ListNode reverseBetween_concise_version(ListNode head, int m, int n) {
-        // use four nodes, pre, start, then, dummy
-        // just reverse the nodes along the way
-        ListNode dummy = new ListNode(-1);
-        dummy.next = head;
-        ListNode pre = dummy;
-        for (int i = 0; i < m - 1; i++) {
-            pre = pre.next;
-        }
-
-        ListNode start = pre.next;// start is the node prior to reversing, in the given example,
-                                  // start is node with value 1
-        ListNode then = start.next;// then is the node that we'll start to reverse, in the given
-                                   // example, it's 2
-
-        for (int i = 0; i < n - m; i++) {
-            // pay special attention to this for loop, it's assigning then.next to start.next, it
-            // didn't initialize a new node
-            // this does exactly what I desired to do, but I just didn't figure out how to implement
-            // it, thumbs up to the OP!
-            start.next = then.next;
-            then.next = pre.next;
-            pre.next = then;
-            then = start.next;
-        }
-
-        return dummy.next;
-    }
-
+  public static class Solution1 {
+    /** credit: https://discuss.leetcode.com/topic/8976/simple-java-solution-with-clear-explanation */
     public ListNode reverseBetween(ListNode head, int m, int n) {
-        // find node at position m, let's call it "revHead"
-        // set its previous node as "newRevHead", then start processing until we reach node at
-        // position n
-        ListNode newRevHead = null;
-        ListNode revHead = head;
-        ListNode pre = new ListNode(-1);
-        pre.next = head;
-        if (m > 1) {
-            int mCnt = 1;
-            while (mCnt++ < m) {
-                newRevHead = revHead;
-                revHead = revHead.next;
-            }
-        }
-        ListNode nodePriorToM = newRevHead;
-
-        // iteratively
-        int nCnt = m;
-        ListNode next = null;
-        while (nCnt <= n) {
-            next = revHead.next;
-            revHead.next = newRevHead;
-            newRevHead = revHead;
-            revHead = next;
-            nCnt++;
-        }
-
-        if (nCnt > n) {
-            nCnt--;
-        }
-        // append next to the tail of the reversed part
-        ListNode reversedPart = newRevHead;
-        if (reversedPart != null) {
-            while (nCnt > m) {
-                reversedPart = reversedPart.next;
-                nCnt--;
-            }
-            reversedPart.next = next;
-        }
-
-        // append the reversed part head to the node at position m-1
-        if (nodePriorToM != null) {
-            nodePriorToM.next = newRevHead;
-        } else {
-            pre.next = newRevHead;
-        }
-
-        return pre.next;
+      // use four nodes, pre, start, then, dummy
+      // just reverse the nodes along the way
+      ListNode dummy = new ListNode(-1);
+      dummy.next = head;
+      ListNode pre = dummy;
+      for (int i = 0; i < m - 1; i++) {
+        pre = pre.next;
+      }
+
+      ListNode start = pre.next;// start is the node prior to reversing, in the given example,
+      // start is node with value 1
+      ListNode then = start.next;// then is the node that we'll start to reverse, in the given
+      // example, it's 2
+
+      for (int i = 0; i < n - m; i++) {
+        // pay special attention to this for loop, it's assigning then.next to start.next, it
+        // didn't initialize a new node
+        // this does exactly what I desired to do, but I just didn't figure out how to implement
+        // it, thumbs up to the OP!
+        start.next = then.next;
+        then.next = pre.next;
+        pre.next = then;
+        then = start.next;
+      }
+
+      return dummy.next;
     }
-
-    public static void main(String... strings) {
-        _92 test = new _92();
-        // ListNode head = new ListNode(1);
-        // head.next = new ListNode(2);
-        // head.next.next = new ListNode(3);
-        // head.next.next.next = new ListNode(4);
-        // head.next.next.next.next = new ListNode(5);
-        // int m = 2, n =4;
-
-        // ListNode head = new ListNode(5);
-        // int m = 1, n =1;
-
-        ListNode head = new ListNode(3);
-        head.next = new ListNode(5);
-        int m = 1;
-        int n = 2;
-
-        CommonUtils.printList(head);
-        ListNode result = test.reverseBetween(head, m, n);
-        CommonUtils.printList(result);
-    }
-
+  }
 }
