Implement a recursive solution

1 files changed, 25 insertions, 0 deletions

diff --git a/2020/08/15/main.rb b/2020/08/15/main.rb
index 909c648..b743d3b 100644
--- a/2020/08/15/main.rb
+++ b/2020/08/15/main.rb
@@ -49,6 +49,31 @@ class Solution
       c.next = n
     end
   end
+
+=begin
+
+         p
+              c
+                   n
+                        t
+[(nil)<-(4)<-(3)<-(2)->(1)->(0)->(nil)]
+
+
+=end
+  def self.swap(c, n, p)
+    return if c.nil?
+
+    t = n&.next
+    c.next = p
+    n&.next = c
+    swap(n, t, c)
+  end
+
+  # time: O(n)
+  # space: O(n)
+  def self.run(head)
+    swap(head, head.next, nil)
+  end
 end
 
 =begin