update 148

fishercoder1534 · fishercoder1534 · commit cc875bd9e900 · 2024-01-27T09:54:04.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_148.java b/src/main/java/com/fishercoder/solutions/_148.java
@@ -2,6 +2,10 @@
 
 import com.fishercoder.common.classes.ListNode;
 
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+
 public class _148 {
 
     public static class Solution1 {
@@ -192,4 +196,29 @@ private ListNode getMid(ListNode head) {
             return mid;
         }
     }
+
+    public static class Solution4 {
+        /**This is the most naive, using O(n) extra memory, O(nlogn) time.*/
+        public ListNode sortList(ListNode head) {
+            if (head == null) {
+                return head;
+            }
+            List<Integer> list = new ArrayList<>();
+            ListNode tmp = head;
+            while (tmp != null) {
+                list.add(tmp.val);
+                tmp = tmp.next;
+            }
+            Collections.sort(list);
+            ListNode pre = new ListNode(-1);
+            ListNode newHead = new ListNode(list.get(0));
+            pre.next = newHead;
+            for (int i = 1; i < list.size(); i++) {
+                ListNode next = new ListNode(list.get(i));
+                newHead.next = next;
+                newHead = newHead.next;
+            }
+            return pre.next;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_148Test.java b/src/test/java/com/fishercoder/_148Test.java
@@ -3,23 +3,25 @@
 import com.fishercoder.common.classes.ListNode;
 import com.fishercoder.common.utils.LinkedListUtils;
 import com.fishercoder.solutions._148;
-import org.junit.BeforeClass;
-import org.junit.Test;
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
 
-import static org.junit.Assert.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertEquals;
 
 public class _148Test {
     private static _148.Solution1 solution1;
     private static _148.Solution2 solution2;
     private static _148.Solution3 solution3;
+    private static _148.Solution4 solution4;
     private static ListNode head;
     private static ListNode expected;
 
-    @BeforeClass
-    public static void setup() {
+    @BeforeEach
+    public void setup() {
         solution1 = new _148.Solution1();
         solution2 = new _148.Solution2();
         solution3 = new _148.Solution3();
+        solution4 = new _148.Solution4();
     }
 
     @Test
@@ -43,4 +45,11 @@ public void test3() {
         assertEquals(expected, solution3.sortList(head));
     }
 
+    @Test
+    public void test4() {
+        head = LinkedListUtils.contructLinkedList(new int[]{4, 2, 1, 3});
+        expected = LinkedListUtils.contructLinkedList(new int[]{1, 2, 3, 4});
+        assertEquals(expected, solution4.sortList(head));
+    }
+
 }
