Merge two sorted lists

Given two sorted lists merge them into a single sorted list

Example

L1: 1,3,5,7,9
L2: 2,4,6,8,10
L3 (merged list): 1,2,3,4,5,6,7,8,9,10

Solution

• Keep tract of curr pointer for L1, L2 and L3 (merged list)
• Find the smaller of the 2 nodes between L1_ptr and L2_ptr
• Append the smaller node to L3, move the respective pointer forward
• Be sure to append any remaining nodes from either list as a last step

Code

def merge(head1, head2)
  curr1 = head1
  curr2 = head2

    if head1.data < head2.data
        head = head1
        curr1 = head1.ptr
    else
        head = head2
        curr2 = head2.ptr
    end

    curr = head

    while curr1 != nil && curr2 != nil
        if(curr1.data < curr2.data)
            curr.ptr = curr1
            curr = curr.ptr
            curr1 = curr1.ptr
        else
            curr.ptr = curr2
            curr = curr.ptr
            curr2 = curr2.ptr
        end
  end

  if curr1 != nil
    append(curr, curr1)
  end

  if curr2 != nil
    append(curr, curr2)
  end

  head
end

def append(curr, curr1)
  while curr1 != nil
    curr.ptr = curr1
    curr = curr.ptr
    curr1 = curr1.ptr
  end
end

Time complexity

• O(n) since we're making a single pass over both the linked lists