{"id":2290,"date":"2025-12-13T15:07:14","date_gmt":"2025-12-13T15:07:14","guid":{"rendered":"https:\/\/www.ignoubcamca.com\/forum\/?p=2290"},"modified":"2025-12-18T17:40:24","modified_gmt":"2025-12-18T17:40:24","slug":"question-1-mcs-209-data-structures-and-algorithms-lab","status":"publish","type":"post","link":"https:\/\/www.ignoubcamca.com\/forum\/question-1-mcs-209-data-structures-and-algorithms-lab\/","title":{"rendered":"Question 1: MCS-209 Data Structures and Algorithms Lab"},"content":{"rendered":"\n

Write an algorithm and program in \u2018C\u2019 language to merge two sorted linked lists. The resultant linked list should be sorted.<\/h2>\n\n\n\n\n\n\n\n

Algorithm to Merge Two Sorted Linked Lists<\/strong><\/h3>\n\n\n\n
    \n
  1. Start.<\/li>\n\n\n\n
  2. Create a node structure with data<\/code> and next<\/code>.<\/li>\n\n\n\n
  3. Create two sorted linked lists (list1<\/code> and list2<\/code>).<\/li>\n\n\n\n
  4. Create a dummy node to store the merged list.<\/li>\n\n\n\n
  5. Set a pointer tail<\/code> to the dummy node.<\/li>\n\n\n\n
  6. Compare the data of the current nodes of both lists:\n
      \n
    • If data of list1<\/code> \u2264 data of list2<\/code>, attach list1<\/code> node to tail<\/code> and move list1<\/code> forward.<\/li>\n\n\n\n
    • Else, attach list2<\/code> node to tail<\/code> and move list2<\/code> forward.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
    • Move tail<\/code> to the newly added node.<\/li>\n\n\n\n
    • Repeat steps 6\u20137 until one list becomes empty.<\/li>\n\n\n\n
    • Attach the remaining nodes of the non-empty list to tail<\/code>.<\/li>\n\n\n\n
    • The merged sorted list starts from dummy->next<\/code>.<\/li>\n\n\n\n
    • Stop.<\/li>\n<\/ol>\n\n\n\n

      C Program to Merge Two Sorted Linked Lists<\/strong><\/h2>\n\n\n\n
      C Program to Merge Two Sorted Linked Lists
      #include <stdio.h>
      #include <stdlib.h>

      \/\/ Definition of linked list node
      struct Node {
          int data;
          struct Node* next;
      };

      \/\/ Function to create a new node
      struct Node* createNode(int data) {
          struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
          newNode->data = data;
          newNode->next = NULL;
          return newNode;
      }

      \/\/ Function to merge two sorted linked lists
      struct Node* mergeSortedLists(struct Node* list1, struct Node* list2) {
          struct Node dummy;
          struct Node* tail = &dummy;
          dummy.next = NULL;

          while (list1 != NULL && list2 != NULL) {
              if (list1->data <= list2->data) {
                  tail->next = list1;
                  list1 = list1->next;
              } else {
                  tail->next = list2;
                  list2 = list2->next;
              }
              tail = tail->next;
          }

          \/\/ Attach remaining nodes
          if (list1 != NULL)
              tail->next = list1;
          else
              tail->next = list2;

          return dummy.next;
      }

      \/\/ Function to display the linked list
      void display(struct Node* head) {
          while (head != NULL) {
              printf(\"%d -> \", head->data);
              head = head->next;
          }
          printf(\"NULL\\n\");
      }

      \/\/ Main function
      int main() {
          \/\/ Creating first sorted list: 1 -> 3 -> 5
          struct Node* list1 = createNode(1);
          list1->next = createNode(3);
          list1->next->next = createNode(5);

          \/\/ Creating second sorted list: 2 -> 4 -> 6
          struct Node* list2 = createNode(2);
          list2->next = createNode(4);
          list2->next->next = createNode(6);

          printf(\"List 1: \");
          display(list1);

          printf(\"List 2: \");
          display(list2);

          \/\/ Merging the lists
          struct Node* mergedList = mergeSortedLists(list1, list2);

          printf(\"Merged Sorted List: \");
          display(mergedList);

          return 0;
      }<\/pre>\n\n\n\n
      Output Example<\/p>\n\n\n\n
      List 1: 1 -> 3 -> 5 -> NULL
      List 2: 2 -> 4 -> 6 -> NULL
      Merged Sorted List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL<\/code><\/p>\n","protected":false},"excerpt":{"rendered":"
      Write an algorithm and program in \u2018C\u2019 language to merge two sorted linked lists. The
      \nresultant linked list should be sorted.<\/p>\n","protected":false},"author":1,"featured_media":2352,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[29,30],"tags":[],"class_list":["post-2290","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-bca-assignment","category-january-2026"],"_links":{"self":[{"href":"https:\/\/www.ignoubcamca.com\/forum\/wp-json\/wp\/v2\/posts\/2290","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.ignoubcamca.com\/forum\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.ignoubcamca.com\/forum\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.ignoubcamca.com\/forum\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.ignoubcamca.com\/forum\/wp-json\/wp\/v2\/comments?post=2290"}],"version-history":[{"count":2,"href":"https:\/\/www.ignoubcamca.com\/forum\/wp-json\/wp\/v2\/posts\/2290\/revisions"}],"predecessor-version":[{"id":2310,"href":"https:\/\/www.ignoubcamca.com\/forum\/wp-json\/wp\/v2\/posts\/2290\/revisions\/2310"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.ignoubcamca.com\/forum\/wp-json\/wp\/v2\/media\/2352"}],"wp:attachment":[{"href":"https:\/\/www.ignoubcamca.com\/forum\/wp-json\/wp\/v2\/media?parent=2290"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ignoubcamca.com\/forum\/wp-json\/wp\/v2\/categories?post=2290"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ignoubcamca.com\/forum\/wp-json\/wp\/v2\/tags?post=2290"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}