title: Merging two sorted linked lists
body: <p>This is one of the programming questions asked during written test from Microsoft. I am giving the question and the answer that I came up with. Thing is my answer although looks comprehensive (at least to me), I feel that the number of lines can be reduced. It was asked in C and I am a Java person but I managed to code it (my answer may contain too many Java like syntaxes)</p>
  
  <p>Ok, here is the question.</p>
  
  <blockquote>
    <p>You have two lists that are already
    sorted, you have to merge them and
    return a new list without any new extra
    nodes. The returned list should be 
    sorted as well. </p>
  </blockquote>
  
  <p>The method signature is,</p>
  
  <pre><code>Node* MergeLists(Node* list1, Node* list2);
  
  struct Node{
      int data;
      Node *next;
  }
  </code></pre>
  
  <p>The following is the solution I came up with,</p>
  
  <pre><code>Node* MergeLists(Node* list1, Node* list2){
      Node* mergedList;
      if(list1 == null &amp;&amp; list2 ==null){//if both are null, return null
          return null;
      }
      if(list1 == null){//if list1 is null, simply return list2
          return list2;
      }
      if(list2 == null){//if list2 is null, simply return list1
          return list1;
      }
      if(list1.data &lt; list2.data){//initialize mergedList pointer to list1 if list1's data is lesser
          mergedList = list1;
      }else{//initialize mergedList pointer to list2 if list2's data is lesser or equal
          mergedList = list2;
      }
      while(list1!=null &amp;&amp; list2!=null){
          if(list1.data &lt; list2.data){
              mergedList-&gt;next = list1;
              list1 = list1-&gt;next;
          }else{
              mergedList-&gt;next = list2;
              list2 = list2-&gt;next;
          }
      }
      if(list1 == null){//remaining nodes of list2 appended to mergedList when list1 has reached its end.
          mergedList-&gt;next = list2;
      }else{//remaining nodes of list1 appended to mergedList when list2 has reached its end
          mergedList-&gt;next = list1;
      }
      return mergedList;
  }
  </code></pre>
  
  <p>I am very confident this can be enhanced. Please help me find what lines are redundantly I've added. Please feel free to criticize my syntax errors and logic.</p>
  
  <p>Thanks!</p>