title: Time Complexity?
body: <p>Problem was to find the intersection of 2 sorted linked lists and store the common elements in the third list.</p>
  
  <p>My approach was to make temporary pointers <code>temp1</code> and <code>temp2</code> initializing both to <code>head1</code> (head of list 1) and <code>head2</code> (head of list 2) respectively.And then traversing both lists and comparing elements and shifting <code>temp1</code> and <code>temp2</code> accordingly.The code works fine.</p>
  
  <p>Test case:
  First linked list=> 1->2->3->4->6 
  Second linked list be 2->4->6->8, then  function should create and return a third list as 2->4->6.</p>
  
  <p>But I am confused about what is the time complexity: <strong>O(m+n)</strong> or <strong>O(min(m,n))</strong>? (m,n are number of elements in list 1 and list 2).</p>
  
  <p>My Code:</p>
  
  <pre><code>#include&lt;stdio.h&gt;
  #include&lt;stdlib.h&gt;
  
  /* Link list node */
  struct Node
  {
      int data;
      struct Node* next;
  };
  void append(struct Node** head_ref, int new_data)
  {
      /* 1. allocate node */
      struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
  
      struct Node *last = *head_ref;  /* used in step 5*/
  
      /* 2. put in the data  */
      new_node-&gt;data  = new_data;
  
      /* 3. This new node is going to be the last node, so make next 
            of it as NULL*/
      new_node-&gt;next = NULL;
  
      /* 4. If the Linked List is empty, then make the new node as head */
      if (*head_ref == NULL)
      {
         *head_ref = new_node;
         return;
      }  
  
      /* 5. Else traverse till the last node */
      while (last-&gt;next != NULL)
          last = last-&gt;next;
  
      /* 6. Change the next of last node */
      last-&gt;next = new_node;
      return;    
  }
  
  struct Node* sortedIntersect(struct Node* head1,struct Node*head2)
  {
      struct Node*head3=NULL;
      struct Node*temp1=head1;
      struct Node*temp2=head2;
      while(temp1!=NULL&amp;&amp;temp2!=NULL)
      {
          if(temp1-&gt;data&lt;temp2-&gt;data)
          {if(temp1-&gt;next!=NULL)
              temp1=temp1-&gt;next;
              else
              break;
          } 
          else if(temp1-&gt;data&gt;temp2-&gt;data)
          {
              if(temp2-&gt;next!=NULL)
              temp2=temp2-&gt;next;
              else{
                  break;
              }
          }
          else 
          {
              append(&amp;head3,temp1-&gt;data);
              temp1=temp1-&gt;next;
              temp2=temp2-&gt;next;
          }
      }
      return head3;
  }
  
  
  /* Function to insert a node at the beginging of the linked list */
  void push(struct Node** head_ref, int new_data)
  {
      /* allocate node */
      struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
  
      /* put in the data */
      new_node-&gt;data = new_data;
  
      /* link the old list off the new node */
      new_node-&gt;next = (*head_ref);
  
      /* move the head to point to the new node */
      (*head_ref) = new_node;
  }
  
  /* Function to print nodes in a given linked list */
  void printList(struct Node *node)
  {
      while (node != NULL)
      {
          printf("%d ", node-&gt;data);
          node = node-&gt;next;
      }
  }
  
  
  int main()
  {
      /* Start with the empty lists */
      struct Node* a = NULL;
      struct Node* b = NULL;
      struct Node *intersect = NULL;
  
      /* Let us create the first sorted linked list to test the functions
      Created linked list will be 1-&gt;2-&gt;3-&gt;4-&gt;5-&gt;6 */
      push(&amp;a, 6);
      push(&amp;a, 5);
      push(&amp;a, 4);
      push(&amp;a, 3);
      push(&amp;a, 2);
      push(&amp;a, 1);
  
      /* Let us create the second sorted linked list
      Created linked list will be 2-&gt;4-&gt;6-&gt;8 */
      push(&amp;b, 8);
      push(&amp;b, 6);
      push(&amp;b, 4);
      push(&amp;b, 2);
  
      /* Find the intersection two linked lists */
      intersect = sortedIntersect(a, b);
  
      printf("\n Linked list containing common items of a &amp; b \n ");
      printList(intersect);
  
      return 0;
  }
  </code></pre>