[Algorithm] Merge two sorted link list without using recursion

Algorithm

First 15 Minutes Free

Shikhill Gupta

★ ★ ★ ★ ★

View Profile Sign Up to Contact

32 sessions given
since Apr 25, 2015

Response Time: within an hour

Shikhill Gupta

Sep 12, 2015

#include <iostream>   class Node;   Node * CreateLinkList(int array[], int length); Node* Merge (Node* head1, Node* head2);   void printNodes(Node * head);   class Node {     public:         int data;         Node* Next; };   int main(int argc, const char * argv[]) {     // insert code here...         int array1[4] = {3,6,8,9};     int array2[5] = {2,5,7,9,10};          Node * head1 = CreateLinkList(array1, 4);          Node * head2 = CreateLinkList(array2, 1);          Node * head3 = Merge(head1, head2);          printNodes(head3);          getchar();     return 0; }   Node * CreateLinkList(int array[], int length) {     Node * head = NULL;     Node * current = NULL;          for (int i = 0; i<length; i++) {         Node * node = (Node *)malloc(sizeof(Node));         node->data = array[i];         node->Next = NULL;         if (head == NULL) {             head = node;             current = node;         }         else {             current->Next = node;             current = node;         }              }     return head; } void printNodes(Node * head) {     while (head != NULL) {         std::cout<<head->data <<"-->";         head = head->Next;     }     std::cout<<"\n"; }   Node* Merge (Node* head1, Node* head2) {          Node * newHead = NULL;     Node * current = NULL;         while (head1 != NULL || head2 != NULL) {                  if(head1 != NULL && head2  != NULL) {             if(head1->data >= head2->data) {                 if(current == NULL){                     newHead = head2;                     head2 = head2->Next;                     current = newHead;                     current->Next = NULL;                 }                 else {                                          current->Next = head2;                     current = head2;                     head2 = head2->Next;                     current->Next = NULL;                 }             }             else {                     if(current == NULL){                         newHead = head1;                         head1 = head1->Next;                         current = newHead;                         current->Next = NULL;                     }                     else {                                                  current->Next = head1;                         current = head1;                         head1 = head1->Next;                         current->Next = NULL;                     }             }         }         else {             if(head1 == NULL)                 if(newHead == NULL){                     newHead = head2;                     current = head2;                     head2 = head2->Next;                     current->Next = NULL;                                     }                 else {                     current->Next = head2;                     current = head2;                     head2 = head2->Next;                 }             else                 if(head2 ==  NULL) {                     if(newHead == NULL) {                         newHead = head1;                         current = head1;                         head1 = head1->Next;                         current->Next = NULL;                     }                     else {                         current->Next = head1;                         current = head1;                         head1 = head1->Next;                     }                 }                      }              }     return newHead; }

[Algorithm] Merge two sorted link list without using recursion

Share this

Experts Can Help You With

Please accept our cookies! 🍪