Merge two sorted linked lists such that merged list is in reverse order - GeeksforGeeks
Given two linked lists sorted in increasing order. Merge them such a way that the result list is in decreasing order (reverse order).
Read full article from Merge two sorted linked lists such that merged list is in reverse order - GeeksforGeeks
Given two linked lists sorted in increasing order. Merge them such a way that the result list is in decreasing order (reverse order).
// Given two non-empty linked lists 'a' and 'b'Node* SortedMerge(Node *a, Node *b){ // If both lists are empty if (a==NULL && b==NULL) return NULL; // Initialize head of resultant list Node *res = NULL; // Traverse both lists while both of then // have nodes. while (a != NULL && b != NULL) { // If a's current value is smaller or equal to // b's current value. if (a->key <= b->key) { // If this is the first Node to be added to // result list 'res' if (res == NULL) { // Make 'a' as head of result list res = a; // Move ahead in first list a = a->next; res->next = NULL; } else // If there are already Nodes in 'res' { // Store next of current Node in first list Node *temp = a->next; // Add 'a' at the front of resultant list a->next = res; res = a; // Move ahead in first list a = temp; } } // If a's value is greater. Below steps are similar // to above (Only 'a' is replaced with 'b') else { if (res == NULL) { res = b; b = b->next; res->next = NULL; } else { Node *temp = b->next; b->next = res; res = b; b = temp; } } } // If second list reached end, but first list has // nodes. Add remaining nodes of first list at the // front of result list while (a != NULL) { Node *temp = a->next; a->next = res; res = a; a = temp; } // If first list reached end, but second list has // node. Add remaining nodes of first list at the // front of result list while (b != NULL) { Node *temp = b->next; b->next = res; res = b; b = temp; } return res;}