#include <stdio.h>
#include <stdlib.h>
// Structure for a node in the singly linked list
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));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to insert a node at the end
void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
// 1. Traversal: Print all elements in the linked list
void traverseList(struct Node* head) {
if (head == NULL) {
printf("List is empty\n");
return;
}
printf("Linked List: ");
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
// 2. Find the length of the linked list
int getLength(struct Node* head) {
int length = 0;
struct Node* temp = head;
while (temp != NULL) {
length++;
temp = temp->next;
}
return length;
}
// 3. Search for an element in the linked list
int searchElement(struct Node* head, int key) {
struct Node* temp = head;
int position = 1;
while (temp != NULL) {
if (temp->data == key) {
return position;
}
temp = temp->next;
position++;
}
return -1; // Element not found
}
// 4. Find the middle element of the linked list (Slow and Fast Pointer)
int findMiddle(struct Node* head) {
if (head == NULL) {
printf("List is empty\n");
return -1;
}
struct Node *slow = head, *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow->data;
}
// 5. Detect a loop in the linked list (Floyd’s Cycle Detection)
int detectLoop(struct Node* head) {
struct Node *slow = head, *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return 1; // Loop detected
}
}
return 0; // No loop
}
// 6. Merge two sorted linked lists
struct Node* mergeSortedLists(struct Node* head1, struct Node* head2) {
struct Node dummy;
struct Node* tail = &dummy;
dummy.next = NULL;
while (head1 != NULL && head2 != NULL) {
if (head1->data <= head2->data) {
tail->next = head1;
head1 = head1->next;
} else {
tail->next = head2;
head2 = head2->next;
}
tail = tail->next;
}
// Attach remaining nodes
if (head1 != NULL) {
tail->next = head1;
} else {
tail->next = head2;
}
return dummy.next;
}
// Main function to test the linked list operations
int main() {
// Create first linked list: 1 -> 3 -> 5 -> 7
struct Node* head1 = NULL;
insertAtEnd(&head1, 1);
insertAtEnd(&head1, 3);
insertAtEnd(&head1, 5);
insertAtEnd(&head1, 7);
// Create second linked list: 2 -> 4 -> 6
struct Node* head2 = NULL;
insertAtEnd(&head2, 2);
insertAtEnd(&head2, 4);
insertAtEnd(&head2, 6);
// 1. Traversal
printf("First ");
traverseList(head1);
printf("Second ");
traverseList(head2);
// 2. Length of the first linked list
printf("Length of first linked list: %d\n", getLength(head1));
// 3. Search for an element
int key = 5;
int pos = searchElement(head1, key);
if (pos != -1) {
printf("Element %d found at position %d in first list\n", key, pos);
} else {
printf("Element %d not found in first list\n", key);
}
// 4. Find middle element
printf("Middle element of first list: %d\n", findMiddle(head1));
// 5. Detect loop (create a loop for testing)
struct Node* temp = head1;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = head1->next; // Create a loop (7 -> 3)
printf("Loop detected in first list: %s\n", detectLoop(head1) ? "Yes" : "No");
temp->next = NULL; // Remove the loop for further operations
// 6. Merge two sorted linked lists
printf("\nMerging two sorted lists:\n");
struct Node* mergedHead = mergeSortedLists(head1, head2);
traverseList(mergedHead);
return 0;
}
Output:
Comments
Post a Comment