Question:
Write a function in C++ to merge two already sorted linked lists, do not use recursion.

Given a data structure:
class Node {
public:
int data;                             Node* next;
};

Implement the function:
Node* Merge (Node* head1, Node* head2)
{
…
}

It takes in two already sorted linked lists (in ascendant order, duplicates allowed) and is supposed to merge them into a single sorted linked list (in ascendant order, duplicates allowed) and returns the new head.

Answer:

Node* Merge(Node* head1, Node* head2)
{
  if (!head1)
    return head2;
  if (!head2)
    return head1;
  Node* merge_head = 0;
  if (head1->data < head2->data) {
    merge_head = head1;
    head1 = head1->next;
  } else {
    merge_head = head2;
    head2 = head2->next;
  }
  Node* merge_tail = merge_head;
  while (head1 && head2) {
    if (head1->data < head2->data) {
      merge_tail->next = head1;
      head1 = head1->next;
    } else {
      merge_tail->next = head2;
      head2 = head2->next;
    }
    merge_tail = merge_tail->next;
  }
  if (head1)
    merge_tail->next = head1;
  if (head2)
    merge_tail->next = head2;
  return merge_head;
}