Merging two sorted linked list

Question: given two sorted linked lists. Merge one to another, so that the result is a sorted linked list.

Let's take a simple case where we have two linked lists of integer such that list1 = 1->3->5->7 and list2 = 1->2->4. Our algorithm must take in these two lists and output either list1 or list2. the catch is that the result must be 1->1->2->3->4->5->7. The result contains all elements of both lists in sorted order.

Assume that we have class called Node such that a Node has a data and next field. data is used to hold an integer and next is the pointer to the next node in the list. Here is one of the solutions to this question written in C++

Node* MergeTwoSortedList(Node* list1, Node* list2)
{
    Node* temp = NULL; //temporary pointer
    Node* slow = NULL; //slow and fast pointer to travel list2
    Node* fast = NULL; 
    Node* head = list2; //keep track the head of the new list2
    
    //merge list1 to list2
    while(list1)
    {
        if(list1->data <= list2->data)
        {
          temp = list1;
          list1 = list1->next;
          temp->next = NULL;
          temp->next = list2;
          list2 = temp;
          head = list2; //update the head pointer
        }
        else
        {
          slow = list2;
          fast = list2->next;
          while(fast != NULL && fast->data <= list1->data)
          {
            slow = slow->next;
            fast = fast->next;
          }
          temp = list1;
          list1 = list1->next;
          temp->next = fast;
          slow->next = temp;
          list2 = temp;
        }
    }
    return head;
}

Explanation:

1. Loop through list1 and examine each node's value. If the current node's value in list1 is smaller or equal to the current node in list2, then we add it to list2 before the current node in list2. After that, we update pointers to the next node in list1 and list2.
2. However, if the current node in list1 is greater than the current node in list2, we'll traverse list2 using slow and fast pointer until our fast pointer is null or is at a node that is greater than the current node in list1. Next, we add the current node in list1 in front of the node pointed to by the slow pointer in list2. Finally, we update the current node in list2 to the node we just took from list1 and the current node in list1 to the next node in list1.
3. In the end, we return head which is the pointer to the head of the new list2 which has all elements from list1 and the old list2 in sorted order.