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;
}