Merge algorithm–Using linked list

This is the most common interview question and most commonly required algorithm for writing any code.

Metaphor

    Consider you are planning a trip in office and got 2 lists which has names listed on it in alphabetical order. You need to merge these two files to get a master participant list. Now, for this you can do a simple merge of the two lists to generate a single list.

Concept

  For merging two lists is a most common algorithm required in many programs. Its similar to the merge algorithm over array where we split the list into 2 and merge. Here, we get 2 lists. We just merge them into a single list and return it.

Code

Using extra memory

   1:   

   2:  List* merge_lists(List *a1, List *a2)

   3:  {

   4:      List *c = 0;

   5:      while(a1 !=0 && a2!=0)

   6:      {

   7:          if(a1->data > a2->data)

   8:          {

   9:              if(c == 0)

  10:                  c=createNode(a2->data);

  11:              else {

  12:                  append(c, createNode(a2->data));

  13:              }

  14:   

  15:              a2 = a2->next;

  16:          }

  17:          else

  18:          {

  19:              if(c == 0)

  20:                  c=createNode(a1->data);

  21:              else {

  22:                  append(c, createNode(a1->data));

  23:              }

  24:   

  25:              a1 = a1->next;

  26:          }

  27:      }

  28:   

  29:      List *iter = c;

  30:      while(iter->next !=0) iter = iter->next;

  31:      if(a2 != 0)

  32:          iter->next = a2;

  33:      else

  34:          iter->next = a1;

  35:      return c;

  36:  }

  37:   

  38:  void main()

  39:  {

  40:      List *list1 = createNode(2);

  41:      append(list1, createNode(3));

  42:      append(list1, createNode(5));

  43:      append(list1, createNode(10));

  44:   

  45:      List *list2 = createNode(1);

  46:      append(list2, createNode(4));

  47:      append(list2, createNode(9));

  48:      append(list2, createNode(12));

  49:   

  50:      List *list3 = merge_lists(list1, list2);

  51:  }

There are interview questions like merge a1 and a2 and place it in a1 without using extra space. We will discuss about this tomorrow.

Important points

• Merge algorithm on-place is very complex and mostly theoretical. We will concentrate on interview questions like How to sort 100GB worth of strings in the coming articles.
• Note that the remaining list at the end is blindly appended to the new list.