Problem of the Day
A new programming or logic puzzle every Mon-Fri

You are given a single linked list which is split in to two sorted parts. Your goal is to write a function to merge the two parts in to one sorted list. Here is an example:

//Input
1->2->3->16->2->3->17

//Output
1->2->2->3->3->16->17

Comments:

• Adam - 10 years, 8 months ago

  Haskell!

  main = do
      let input = [1, 2, 3, 16, 2, 3, 17]
      putStrLn . show . sortSplit $ input
  
  sortSplit :: Ord a => [a] -> [a]
  sortSplit = interleaveSorted . split
  
  interleaveSorted :: Ord a => ([a], [a]) -> [a]
  interleaveSorted (xs@(x:xrest), ys@(y:yrest))
      | y > x     = x : interleaveSorted (xrest, ys)
      | otherwise = y : interleaveSorted (xs, yrest)
  interleaveSorted (xs, []) = xs
  interleaveSorted ([], ys) = ys
  
  split :: Ord a => [a] -> ([a], [a])
  split [] = ([], [])
  split [x] = ([x], [])
  split (x:y:rest) | y > x = (x:xs, ys)
                   | otherwise = ([x], y:rest)
                   where (xs, ys) = split (y:rest)
  

  reply permalink

• Will - 10 years, 8 months ago

  LISP -- a little cheaty, but hey. :)

  ;; Tail-recursively splits a list into two sorted lists.
  (defun split-helper (L list-acc prev)
    (if (and (not (null prev)) (> prev (car L)))
        (list list-acc L)
        (split-helper (cdr L) (append list-acc (list (car L))) (car L))))
  
  (defun split (L)
    (split-helper L '() nil))
  
  
  ;; Merges the two sorted parts of a linked list into a sorted list.
  ;; e.g.:
  ;; CL-USER> (merge-lists '(1 2 3 16 2 3 17))
  ;; (1 2 2 3 3 16 17)
  ;;
  (defun merge-lists (L)
    (let* ((split-lists (split L))
       (L1 (first split-lists))
       (L2 (second split-lists)))
      (merge 'list L1 L2 #'<)))
  

  reply permalink