1.
Merge Two Sorted Lists
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *create(int data) {
struct node *newnode = (struct node *)malloc(sizeof(struct node));
newnode->data = data;
newnode->next = NULL;
return newnode;
}
struct node *merge(struct node *head1, struct node *head2) {
if (!head1) return head2;
if (!head2) return head1;
if (head1->data <= head2->data) {
head1->next = merge(head1->next, head2);
return head1;
} else {
head2->next = merge(head1, head2->next);
return head2;
}
}
void display(struct node *head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
}
int main() {
int a;
struct node *head1 = NULL, *cur1 = NULL;
struct node *head2 = NULL, *cur2 = NULL;
while (1) {
scanf("%d", &a);
if (a == -1) break;
struct node *newnode = create(a);
if (!head1) head1 = cur1 = newnode;
else {
cur1->next = newnode;
cur1 = newnode;
}
}
while (1) {
scanf("%d", &a);
if (a == -1) break;
struct node *newnode = create(a);
if (!head2) head2 = cur2 = newnode;
else {
cur2->next = newnode;
cur2 = newnode;
}
}
struct node *merged = merge(head1, head2);
display(merged);
return 0;
}
2. Remove N-th Node from End
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *create(int val) {
struct node *newnode = (struct node*)malloc(sizeof(struct node));
newnode->data = val;
newnode->next = NULL;
return newnode;
}
void display(struct node *head) {
while (head) {
printf("%d ", head->data);
head = head->next;
}
}
struct node* removeNthFromEnd(struct node* head, int n) {
struct node *dummy = create(0);
dummy->next = head;
struct node *first = dummy, *second = dummy;
for (int i = 0; i <= n; i++)
first = first->next;
while (first != NULL) {
first = first->next;
second = second->next;
}
struct node *toDelete = second->next;
second->next = toDelete->next;
free(toDelete);
return dummy->next;
}
int main() {
int val, n;
struct node *head = NULL, *cur = NULL;
while (1) {
scanf("%d", &val);
if (val == -1) break;
struct node *newnode = create(val);
if (!head) head = cur = newnode;
else {
cur->next = newnode;
cur = newnode;
}
}
scanf("%d", &n);
head = removeNthFromEnd(head, n);
display(head);
return 0;
}
3. Sort 0s, 1s and 2s in Linked List
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *create(int val) {
struct node *newnode = (struct node *)malloc(sizeof(struct node));
newnode->data = val;
newnode->next = NULL;
return newnode;
}
void display(struct node *head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
}
void sort012(struct node *head) {
int count[3] = {0};
struct node *temp = head;
while (temp != NULL) {
count[temp->data]++;
temp = temp->next;
}
temp = head;
for (int i = 0; i < 3; i++) {
while (count[i]--) {
temp->data = i;
temp = temp->next;
}
}
}
int main() {
int val;
struct node *head = NULL, *cur = NULL;
while (1) {
scanf("%d", &val);
if (val == -1) break;
struct node *newnode = create(val);
if (!head) head = cur = newnode;
else {
cur->next = newnode;
cur = newnode;
}
}
sort012(head);
display(head);
return 0;
}
4. Reverse a Linked List
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *create(int val) {
struct node *newnode = (struct node *)malloc(sizeof(struct node));
newnode->data = val;
newnode->next = NULL;
return newnode;
}
void display(struct node *head) {
while (head) {
printf("%d ", head->data);
head = head->next;
}
}
struct node* reverse(struct node *head) {
struct node *prev = NULL, *curr = head, *next = NULL;
while (curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
int main() {
int val;
struct node *head = NULL, *cur = NULL;
while (1) {
scanf("%d", &val);
if (val == -1) break;
struct node *newnode = create(val);
if (!head) head = cur = newnode;
else {
cur->next = newnode;
cur = newnode;
}
}
head = reverse(head);
display(head);
return 0;
}
5. Detect Cycle in Linked List
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *create(int val) {
struct node *newnode = (struct node *)malloc(sizeof(struct node));
newnode->data = val;
newnode->next = NULL;
return newnode;
}
int hasCycle(struct node *head) {
struct node *slow = head;
struct node *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return 1;
}
return 0;
}
int main() {
int val;
struct node *head = NULL, *cur = NULL, *cycleNode = NULL;
int count = 0;
while (1) {
scanf("%d", &val);
if (val == -1) break;
struct node *newnode = create(val);
if (!head) head = cur = newnode;
else {
cur->next = newnode;
cur = newnode;
}
count++;
if (count == 3) cycleNode = newnode; // cycle after 3 nodes
}
// Uncomment this line to create a cycle
// cur->next = cycleNode;
if (hasCycle(head))
printf("Cycle detected");
else
printf("No cycle");
return 0;
}
