add 430

fishercoder1534 · fishercoder1534 · commit c58a143f9a49 · 2021-10-31T12:27:57.000-07:00
diff --git a/README.md b/README.md
@@ -850,6 +850,7 @@ _If you like this project, please leave me a star._ &#9733;
 |435|[Non-overlapping Intervals](https://leetcode.com/problems/non-overlapping-intervals/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_435.java) |  |Medium| Greedy
 |434|[Number of Segments in a String](https://leetcode.com/problems/number-of-segments-in-a-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_434.java)|  |Easy|
 |432|[All O`one Data Structure](https://leetcode.com/problems/all-oone-data-structure/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_432.java)|  |Hard| Design
+|430|[Flatten a Multilevel Doubly Linked List](https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_430.java)|  |Medium|LinkedList, DFS, Doubly-Linked List 
 |429|[N-ary Tree Level Order Traversal](https://leetcode.com/problems/n-ary-tree-level-order-traversal/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_429.java)|  |Easy| BFS, Tree
 |425|[Word Squares](https://leetcode.com/problems/word-squares/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_425.java)|  |Hard| Trie, Backtracking, Recursion
 |424|[Longest Repeating Character Replacement](https://leetcode.com/problems/longest-repeating-character-replacement/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_424.java)| | Medium| Sliding Window
diff --git a/src/main/java/com/fishercoder/solutions/_430.java b/src/main/java/com/fishercoder/solutions/_430.java
@@ -0,0 +1,45 @@
+package com.fishercoder.solutions;
+
+public class _430 {
+    public static class Solution1 {
+        /**
+         * credit: https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/solution/
+         */
+        public Node flatten(Node head) {
+            if (head == null) {
+                return null;
+            }
+            Node pre = new Node(-1, null, head, null);
+            dfs(pre, head);
+            pre.next.prev = null;
+            return pre.next;
+        }
+
+        private Node dfs(Node prev, Node curr) {
+            if (curr == null) {
+                return prev;
+            }
+            curr.prev = prev;
+            prev.next = curr;
+
+            Node next = curr.next;
+            Node tail = dfs(curr, curr.child);
+            curr.child = null;
+            return dfs(tail, next);
+        }
+    }
+
+    public static class Node {
+        public int val;
+        public Node prev;
+        public Node next;
+        public Node child;
+
+        public Node(int val, Node prev, Node next, Node child) {
+            this.val = val;
+            this.prev = prev;
+            this.next = next;
+            this.child = child;
+        }
+    }
+}
