Merge two sorted lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

For this we create a dummy head before the new list so that we don't have to deal with cases for initializing head of new list. Then new list's head could be returned as dummy head's next node.

# Time complexity: O(n)

def merge_two_lists(l1, l2)
  dummyhead =
  p = dummyhead

  while(!l1.nil? && !l2.nil?)
    if (l1.val < l2.val) = l1
      l1 =
    else = l2
      l2 =
    p =

  if (!l1.nil?) = l1

  if (!l2.nil?) = l2
By @Aniruddha Barapatre in
Tags : #CS, #Data structures, #Linked List,

Comments !