Skip to content

Instantly share code, notes, and snippets.

@johanatan
Created March 11, 2016 23:09
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save johanatan/072eb8b3c91fa4595215 to your computer and use it in GitHub Desktop.
Save johanatan/072eb8b3c91fa4595215 to your computer and use it in GitHub Desktop.
Interview question - merge two sorted linked lists
;; merge two sorted linked lists
;; h1 => 2 => 3 => 5
;; h2 => 4 => 4 => 6 => 7
;; h => 2 => 3 => 4 => 4 => 5 => 6 => 7
(defn splitter [lst1 lst2]
(cond (empty? lst1) [lst2 nil nil]
(empty? lst2) [lst1 nil nil]
:else (let [[l1 l2] (if (< (first lst1) (first lst2)) [lst1 lst2] [lst2 lst1])]
(concat (split-with #(<= % (first l2)) l1) [l2]))))
(defn merge-lists [lst1 lst2]
(let [res (atom [])]
(loop [l1 lst1 l2 lst2]
(let [[final next1 next2] (splitter l1 l2)]
(swap! res conj (vec final))
(if (or next1 next2)
(recur next1 next2))))
(flatten @res)))
(merge-lists [2 3 5] [4 4 6 7])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment