The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Linked List

Problem :-
Merge two sorted linked list.

Solution :-
Logic is pretty trivial in this case. Iterate over the two list simultaneously and compare the data values of the nodes in each list. Then take decision on which node should appear first in the merged list.
See below for the efficient implementation using recusrsive approach.

#include<iostream>
using namespace std;

// list node structure
typedef struct list_node {
   int data;
   struct list_node *next;
}node;

// create new node
node *getNewNode(int data) {
   node *new_node = new node;
   new_node->data = data;
   new_node->next = NULL;
   return new_node;
}


// append a node to the list
void addNodeToList(node **head, int data) {
   if (*head == NULL)
      *head = getNewNode(data);
   else {
      node *ptr = *head;
      while (ptr->next != NULL)
         ptr = ptr->next;
      ptr->next = getNewNode(data);
   }
}

// create a list
node *createList1() {
   node *head = NULL;
   addNodeToList(&head,3);
   addNodeToList(&head,7);
   addNodeToList(&head,11);
   addNodeToList(&head,19);
   addNodeToList(&head,99);
   return head;
}

// create 2nd list
node *createList2() {
   node *head = NULL;
   addNodeToList(&head,1);
   addNodeToList(&head,2);
   addNodeToList(&head,16);
   addNodeToList(&head,37);
   addNodeToList(&head,59);
   return head;
}

// traverse the list
void traverseList(node *head) {
   node *ptr = head;
   while (ptr != NULL) {
      cout<<ptr->data<<" ";
      ptr = ptr->next;
   }
}

// merge the two sorted list
node *mergeList(node *h1,node *h2) {
   if (h2 == NULL) return h1;
   if (h1 == NULL) return h2;
   if(h1->data <= h2->data) {
      h1->next = mergeList(h1->next,h2);
      return h1;
   }
   else {
      h2->next = mergeList(h1,h2->next);
      return h2;
   }
}

// main
main() {
   node *head1 = NULL,*head2 = NULL;
   head1 = createList1();
   head2 = createList2();
   cout<<"\nList 1 :: ";
   traverseList(head1);
   cout<<"\nList 2 :: ";
   traverseList(head2);
   head1 = mergeList(head1,head2);
   cout<<"\nAfter Merging :: ";
   traverseList(head1);
   cout<<endl;
}

Back | Next

All problems on Linked List
* Insert, Delete and Search nodes in a single linked list
* Insert, Delete and Search nodes in a double linked list
* Sort a linked list where each node element is either 1 or 0
* Reverse a linked list in an efficient manner
* Merge two sorted linked lists
* Detect a loop in a given linked list