Linked Lists Basics: Day 10 Challenge

Welcome to Day 10 of the 100 Days DSA Challenge! Today, we will explore the concept of linked lists, an essential data structure used in various applications. We will tackle several fundamental linked list problems using C language. Let's get started!

1. Implement a Singly Linked List

Problem: Implement a singly linked list with operations for insertion, deletion, and traversal.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

void insert(struct Node** head, int data) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}

void delete(struct Node** head, int key) {
    struct Node* temp = *head;
    struct Node* prev = NULL;

    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }

    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) return;

    prev->next = temp->next;
    free(temp);
}

void traverse(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;

    insert(&head, 1);
    insert(&head, 2);
    insert(&head, 3);
    printf("Linked list: ");
    traverse(head);

    delete(&head, 2);
    printf("After deletion: ");
    traverse(head);

    return 0;
}

2. Reverse a Linked List

Problem: Write a program to reverse a linked list.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

void reverse(struct Node** head) {
    struct Node* prev = NULL;
    struct Node* current = *head;
    struct Node* next = NULL;

    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    *head = prev;
}

void insert(struct Node** head, int data) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}

void traverse(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;

    insert(&head, 1);
    insert(&head, 2);
    insert(&head, 3);
    printf("Original linked list: ");
    traverse(head);

    reverse(&head);
    printf("Reversed linked list: ");
    traverse(head);

    return 0;
}

3. Detect a Cycle in a Linked List

Problem: Solve the "detect a cycle in a linked list" problem using Floyd’s Cycle Detection algorithm.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

int detectCycle(struct Node* head) {
    struct Node* slow = head;
    struct Node* fast = head;

    while (slow && fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            return 1; // Cycle detected
        }
    }
    return 0; // No cycle
}

void insert(struct Node** head, int data) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}

int main() {
    struct Node* head = NULL;

    insert(&head, 1);
    insert(&head, 2);
    insert(&head, 3);
    head->next->next->next = head; // Creating a cycle for testing

    if (detectCycle(head)) {
        printf("Cycle detected\n");
    } else {
        printf("No cycle detected\n");
    }

    return 0;
}

4. Merge Two Sorted Linked Lists

Problem: Write a program to merge two sorted linked lists.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

struct Node* mergeLists(struct Node* l1, struct Node* l2) {
    if (!l1) return l2;
    if (!l2) return l1;

    if (l1->data <= l2->data) {
        l1->next = mergeLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeLists(l1, l2->next);
        return l2;
    }
}

void insert(struct Node** head, int data) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}

void traverse(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* l1 = NULL;
    struct Node* l2 = NULL;

    insert(&l1, 5);
    insert(&l1, 3);
    insert(&l1, 1);

    insert(&l2, 6);
    insert(&l2, 4);
    insert(&l2, 2);

    printf("List 1: ");
    traverse(l1);

    printf("List 2: ");
    traverse(l2);

    struct Node* mergedList = mergeLists(l1, l2);
    printf("Merged list: ");
    traverse(mergedList);

    return 0;
}

5. Find the Middle Element of a Linked List

Problem: Solve the "find the middle element of a linked list" problem.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

void findMiddle(struct Node* head) {
    struct Node* slow = head;
    struct Node* fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    printf("Middle element: %d\n", slow->data);
}

void insert(struct Node** head, int data) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}

void traverse(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;

    insert(&head, 1);
    insert(&head, 2);
    insert(&head, 3);
    insert(&head, 4);
    insert(&head, 5);

    traverse(head);

    findMiddle(head);

    return 0;
}

Conclusion

That wraps up Day 10 of our DSA challenge! We explored various problems related to linked lists and implemented solutions in C language. Linked lists are a fundamental data structure that can be used in many different scenarios, making them an essential tool in our data structures toolkit. Keep practicing, and you'll become more proficient with linked lists and other data structures.

Stay tuned for more exciting problems and solutions as we continue to improve our skills in data structures and algorithms.

Day 10 of the 100 Days DSA Challenge: Linked Lists Basics

Table of contents