Merge Two Sorted Lists
Procedure to merge two sorted linked lists.
void merge(struct node *first, struct node *second) {
// A pointer to keep track of last node of merged list
struct node *last;
// First node of merged list
if (first -> data < second -> data) {
// Set head and tail of merged list
third = last = first;
// Move forward in first list
first = first -> next;
} else {
// Set head and tail of merged list
third = last = second;
// Move forward in second list
second = second -> next;
}
third -> next = NULL;
// Remaining node of merged list
while (first && second) {
if(first -> data < second -> data) {
// Next node will be first's node
last -> next = first;
// Update the last pointer
last = first;
first = first -> next;
} else {
// Next node will be second's node
last -> next = second;
// Update the last pointer
last = second;
second = second -> next;
}
}
// Merging remaining elements of first list (if any)
if (first) {
last -> next = first;
}
// Merging remaining elements of second list (if any)
if (second) {
last -> next = second;
}
}
Contributed by Nitin Ranganath