Question 1: MCS-209 Data Structures and Algorithms Lab

Write an algorithm and program in ‘C’ language to merge two sorted linked lists. The resultant linked list should be sorted.

Algorithm to Merge Two Sorted Linked Lists

1. Start.
2. Create a node structure with data and next.
3. Create two sorted linked lists (list1 and list2).
4. Create a dummy node to store the merged list.
5. Set a pointer tail to the dummy node.
6. Compare the data of the current nodes of both lists:
   • If data of list1 ≤ data of list2, attach list1 node to tail and move list1 forward.
   • Else, attach list2 node to tail and move list2 forward.
7. Move tail to the newly added node.
8. Repeat steps 6–7 until one list becomes empty.
9. Attach the remaining nodes of the non-empty list to tail.
10. The merged sorted list starts from dummy->next.
11. Stop.

C Program to Merge Two Sorted Linked Lists

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;
}

Output Example

List 1: 1 -> 3 -> 5 -> NULL
List 2: 2 -> 4 -> 6 -> NULL
Merged Sorted List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL