Merge lists without using extra space

 

Common Interview question

  Merge two already sorted lists into a single sorted list without using extra space.

Code

The below code uses the memory allocated for a1, a2 to create a new list “c”. It doesn’t use any extra space from the heap which means this merge is RAM efficient. But in performance wise, we need to traverse the end of the list every time to insert the new least of two list element.

   1:  List* merge_list_nospace(List *a1, List *a2)

   2:  {

   3:      List* c=0;

   4:      if(a2==0)

   5:      {

   6:          c=a1;

   7:          return c;

   8:      }

   9:      else if(a1 == 0)

  10:      {    

  11:          c=a2;

  12:          return c;

  13:      }

  14:   

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

  16:      {

  17:          if(a1->data < a2->data)

  18:          {

  19:              if(c == 0) {

  20:                  c = a1;

  21:                  a1=a1->next;

  22:                  c->next = 0;

  23:              } else {

  24:                  List *iter = c;

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

  26:                  iter->next = a1;

  27:                  a1 = a1->next;

  28:                  iter->next->next = 0;

  29:              }

  30:          }

  31:          else

  32:          {

  33:              if(c == 0) {

  34:                  c = a2;

  35:                  a2=a2->next;

  36:                  c->next = 0;

  37:              } else {

  38:                  List *iter = c;

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

  40:                  iter->next = a2;

  41:                  a2 = a2->next;

  42:                  iter->next->next = 0;

  43:              }

  44:          }

  45:      }

  46:      

  47:      List *iter = c;

  48:      if(c != 0)

  49:      {

  50:          while(iter->next !=0) 

  51:              iter = iter->next;

  52:      }

  53:   

  54:      if(a2!=0)

  55:          iter->next=a2;

  56:      else

  57:          iter->next=a1;

  58:   

  59:      return c;

  60:  }

  61:   

  62:  void main()

  63:  {

  64:      List *list1 = createNode(2);

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

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

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

  68:   

  69:      List *list2 = createNode(1);

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

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

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

  73:   

  74:      List *list3 = merge_list_nospace(list1, list2);

  75:  }

Important points

• Note that you should always maintain the head pointer of a list in a variable to iterate across the linked list
• To create a perfect link always, iter->next = <address> is required.
• BUG FIX!!! You need to test for empty lists input of a1 and a2. This is not done in previous case which will lead to null-pointer access crash!!
• IMPORTANT!! AND VERY IMPORTANT!!.. C or C++ if you are not using C++ reference variable, you are not passing by reference. You generally pass everything as value. So you need a double-pointer, if you want to change the value of a pointer. This double pointer is what converted to a reference in C++