title: Big O complexity to merge two lists
body: <p><strong>Given 2 singly linked lists already sorted, merge the lists.</strong></p>
  
  <p>Example:<br>
  list1:  1 2 3 5 7<br>
  list2:  0 4 6 7 10<br>
  --->    0 1 2 3 4 5 6 7 7 10</p>
  
  <p>Despite from the fact that the solution is quite simple and there are several different implementations of the problem with or without using recursion (like this <a href="http://www.geeksforgeeks.org/merge-two-sorted-linked-lists/" rel="nofollow">http://www.geeksforgeeks.org/merge-two-sorted-linked-lists/</a>  see Method 3),</p>
  
  <p><strong>I was wondering what would be the O big complexity of this implementation:</strong></p>
  
  <ol>
  <li>If one of the lists is empty just return the other</li>
  <li>Otherwise insert each node of the second list into the first one using the sortedInsert function which basically scan the list until the right position is found. Because the 2 lists are both already sorted there's no need to compare each time the node with all the nodes in the first list, I can start the comparison from the last added node.</li>
  </ol>
  
  <p>ex: continuing with the previous example if 4 has been already added I can safely start the next comparison from 4:<br>
  list1:  0 1 2 3 <b>4</b> 5 7<br>
  list2:  6 7 10<br>
  now compare 6 with 4 instead with 1 2 3 4....</p>
  
  <p><strong>If I would compare one element with all the elements in the first list it would be O(m*n) with m=#list2 and n=#list1, but considering this "optimisation" what is the complexity?</strong></p>
  
  <p>Implementation:</p>
  
  <pre><code>// Insert a new node in a sorted list
  int sortedInsert(struct ListNode **head, struct ListNode* newNode) {
      int headUpdated = 0;
      struct ListNode *current;
  
      // The list is empty or the new element has to be added as first element
      if (*head == NULL || (*head)-&gt;data &gt;= newNode-&gt;data) {
          newNode-&gt;next = *head;
          *head = newNode;
          headUpdated = 1;
      }
      else {
          // Locate the node before the point of insertion
          current = *head;
          while (current-&gt;next != NULL &amp;&amp; current-&gt;next-&gt;data &lt; newNode-&gt;data)
              current = current-&gt;next;
  
          newNode-&gt;next = current-&gt;next;
          current-&gt;next = newNode;
      }
  
      return headUpdated;
  }
  
  
  struct ListNode *mergeLists(struct ListNode *head1, struct ListNode *head2) {
      if (head1 == NULL)
          return head2;
  
      if (head2 == NULL)
          return head1;
  
      // Store the node in the first list where to start the comparisons
      struct ListNode *first = head1;
  
      while (head2) {
          struct ListNode *head2Next = head2-&gt;next;
  
          printf("Adding %d starting comparison from %d\n", head2-&gt;data, first-&gt;data);
          if (sortedInsert(&amp;first, head2))
              head1 = first;
  
          first = head2;
          head2 = head2Next;
      }
  
      return head1;
  }
  </code></pre>