1<<-DOC
  2Note: Your solution should have O(l1.length + l2.length) time complexity, since this is what you will be asked to accomplish in an interview.
  3
  4Given two singly linked lists sorted in non-decreasing order, your task is to merge them. In other words, return a singly linked list, also sorted in non-decreasing order, that contains the elements from both original lists.
  5
  6Example
  7
  8For l1 = [1, 2, 3] and l2 = [4, 5, 6], the output should be
  9mergeTwoLinkedLists(l1, l2) = [1, 2, 3, 4, 5, 6];
 10For l1 = [1, 1, 2, 4] and l2 = [0, 3, 5], the output should be
 11mergeTwoLinkedLists(l1, l2) = [0, 1, 1, 2, 3, 4, 5].
 12Input/Output
 13
 14[time limit] 4000ms (rb)
 15[input] linkedlist.integer l1
 16
 17A singly linked list of integers.
 18
 19Guaranteed constraints:
 200 ≤ list size ≤ 104,
 21-109 ≤ element value ≤ 109.
 22
 23[input] linkedlist.integer l2
 24
 25A singly linked list of integers.
 26
 27Guaranteed constraints:
 280 ≤ list size ≤ 104,
 29-109 ≤ element value ≤ 109.
 30
 31[output] linkedlist.integer
 32
 33A list that contains elements from both l1 and l2, sorted in non-decreasing order.
 34DOC
 35
 36describe "#merge_two_linked_lists" do
 37  def merge_two_linked_lists(left, right)
 38    return left if right.nil?
 39    return right if left.nil?
 40    result, other = left.value < right.value ? [left, right] : [right, left]
 41
 42    current = result
 43    previous = nil
 44    until other.nil?
 45      if current.value < other.value
 46        if current.next
 47          previous = current
 48          current = current.next
 49        else
 50          current.next = other
 51          break
 52        end
 53      elsif current.value == other.value
 54        tmp = other
 55        other = other.next
 56        tmp.next = current.next
 57        current.next = tmp
 58        previous = current
 59        current = current.next
 60      else
 61        tmp = other
 62        other = other.next
 63        tmp.next = current
 64        previous&.next = tmp
 65        previous = tmp
 66      end
 67    end
 68
 69    result
 70  end
 71
 72  [
 73    { l1: [1, 2, 3], l2: [4, 5, 6], x: [1, 2, 3, 4, 5, 6] },
 74    { l1: [1, 1, 2, 4], l2: [0, 3, 5], x: [0, 1, 1, 2, 3, 4, 5] },
 75    { l1: [5, 10, 15, 40], l2: [2, 3, 20], x: [2, 3, 5, 10, 15, 20, 40] },
 76    { l1: [1, 1], l2: [2, 4], x: [1, 1, 2, 4] },
 77    { l1: [], l2: [1, 1, 2, 2, 4, 7, 7, 8], x: [1, 1, 2, 2, 4, 7, 7, 8] },
 78    { l1: [], l2: [], x: [] },
 79    { l1: [1, 1, 4], l2: [], x: [1, 1, 4] },
 80    { l1: [1, 1], l2: [0], x: [0, 1, 1] },
 81    { l1: [0], l2: [2], x: [0, 2] },
 82    { l1: [1], l2: [-1000000000, 1000000000], x: [-1000000000, 1, 1000000000] },
 83    { l1: [-1, -1, 0, 1], l2: [-1, 0, 0, 1, 1], x: [-1, -1, -1, 0, 0, 0, 1, 1, 1] },
 84    { l1: [-780990573, -670826849, -404817961, 242026249, 731519938], l2: [-815817641, -426491047, 437929670, 520408640], x: [-815817641, -780990573, -670826849, -426491047, -404817961, 242026249, 437929670, 520408640, 731519938] },
 85  ].each do |x|
 86    it do
 87      result = merge_two_linked_lists(ListNode.to_list(x[:l1]), ListNode.to_list(x[:l2])).to_a
 88      expect(result).to eql(x[:x])
 89    end
 90  end
 91
 92  class ListNode
 93    attr_accessor :value, :next
 94
 95    def initialize(value, next_node: nil)
 96      @value = value
 97      @next = next_node
 98    end
 99
100    def to_a
101      result = []
102      current = self
103      until current.nil?
104        result.push(current.value)
105        current = current.next
106      end
107      result
108    end
109
110    def self.to_list(items)
111      x = nil
112      items.inject(nil) do |memo, item|
113        node = new(item)
114        if memo.nil?
115          x = node
116        else
117          memo.next = node
118        end
119        node
120      end
121      x
122    end
123  end
124end