[algorithm] Interview Question: Merge two sorted singly linked lists without creating new nodes

Node MergeLists(Node node1, Node node2)
{
   if(node1 == null)
      return node2;
   else (node2 == null)
      return node1;

   Node head;
   if(node1.data < node2.data)
   {
      head = node1;
      node1 = node1.next;
   else
   {
      head = node2;
      node2 = node2.next;
   }

   Node current = head;
   while((node1 != null) ||( node2 != null))
   {
      if (node1 == null) {
         current.next = node2;
         return head;
      }
      else if (node2 == null) {
         current.next = node1;
         return head;
      }

      if (node1.data < node2.data)
      {
          current.next = node1;
          current = current.next;

          node1 = node1.next;
      }
      else
      {
          current.next = node2;
          current = current.next;

          node2 = node2.next;
      }
   }
   current.next = NULL // needed to complete the tail of the merged list
   return head;

}

Examples related to algorithm

• How can I tell if an algorithm is efficient? • Find the smallest positive integer that does not occur in a given sequence • Efficiently getting all divisors of a given number • Peak signal detection in realtime timeseries data • What is the optimal algorithm for the game 2048? • How can I sort a std::map first by value, then by key? • Finding square root without using sqrt function? • Fastest way to flatten / un-flatten nested JSON objects • Mergesort with Python • Find common substring between two strings

Examples related to singly-linked-list

• Reverse Singly Linked List Java • Interview Question: Merge two sorted singly linked lists without creating new nodes • How to reverse a singly linked list using only two pointers?