#include <stdio.h>
#include <stdlib.h>
// Node structure for the linked list
typedef struct Node {
int data;
struct Node* next;
} Node;
// Function to create a new node
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(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 beginning of the list
void insertAtBeginning(Node** head, int data) {
Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}
// Function to print the linked list
void printList(Node* head) {
Node* current = head;
printf("List: ");
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
// Function to merge two sorted linked lists
Node* merge(Node* left, Node* right) {
if (left == NULL) return right;
if (right == NULL) return left;
Node* result = NULL;
if (left->data <= right->data) {
result = left;
result->next = merge(left->next, right);
} else {
result = right;
result->next = merge(left, right->next);
}
return result;
}
// Function to split the linked list into two halves
void split(Node* source, Node** front, Node** back) {
Node* fast;
Node* slow;
slow = source;
fast = source->next;
// Move fast two nodes and slow one node
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
// Split the list
*front = source;
*back = slow->next;
slow->next = NULL;
}
// Function to sort the linked list using merge sort
void mergeSort(Node** headRef) {
Node* head = *headRef;
Node* left;
Node* right;
// Base case: if head is NULL or only one element
if (head == NULL || head->next == NULL) {
return;
}
// Split the list into two halves
split(head, &left, &right);
// Recursively sort both halves
mergeSort(&left);
mergeSort(&right);
// Merge the sorted halves
*headRef = merge(left, right);
}
// Function to remove the first occurrence of a value
Node* removeByValue(Node* head, int value) {
// If list is empty
if (head == NULL) {
printf("List is empty\n");
return head;
}
// If the head node contains the value to be removed
if (head->data == value) {
Node* temp = head;
head = head->next;
free(temp);
printf("Removed %d from the list\n", value);
return head;
}
// Search for the node to be removed
Node* current = head;
while (current->next != NULL && current->next->data != value) {
current = current->next;
}
// If value not found
if (current->next == NULL) {
printf("Value %d not found in the list\n", value);
return head;
}
// Remove the node
Node* nodeToRemove = current->next;
current->next = nodeToRemove->next;
free(nodeToRemove);
printf("Removed %d from the list\n", value);
return head;
}
// Function to remove node at a specific position (0-indexed)
Node* removeAtPosition(Node* head, int position) {
// If list is empty
if (head == NULL) {
printf("List is empty\n");
return head;
}
// If removing the head node
if (position == 0) {
Node* temp = head;
head = head->next;
printf("Removed node at position %d (value: %d)\n", position, temp->data);
free(temp);
return head;
}
// Find the node at the given position
Node* current = head;
for (int i = 0; current != NULL && i < position - 1; i++) {
current = current->next;
}
// If position is out of bounds
if (current == NULL || current->next == NULL) {
printf("Position %d is out of bounds\n", position);
return head;
}
// Remove the node
Node* nodeToRemove = current->next;
current->next = nodeToRemove->next;
printf("Removed node at position %d (value: %d)\n", position, nodeToRemove->data);
free(nodeToRemove);
return head;
}
// Function to free the entire linked list
void freeList(Node* head) {
Node* current = head;
Node* next;
while (current != NULL) {
next = current->next;
free(current);
current = next;
}
}
// Main function to demonstrate the linked list operations
int main() {
Node* head = NULL;
// Insert some values
insertAtBeginning(&head, 64);
insertAtBeginning(&head, 34);
insertAtBeginning(&head, 25);
insertAtBeginning(&head, 12);
insertAtBeginning(&head, 22);
insertAtBeginning(&head, 11);
insertAtBeginning(&head, 90);
printf("Original ");
printList(head);
// Sort the list
mergeSort(&head);
printf("Sorted ");
printList(head);
// Remove by value
head = removeByValue(head, 25);
printList(head);
// Remove by position
head = removeAtPosition(head, 2);
printList(head);
// Try to remove a non-existent value
head = removeByValue(head, 100);
// Try to remove at invalid position
head = removeAtPosition(head, 10);
// Free the memory
freeList(head);
return 0;
}