Table of contents
- Q1. Implement a singly linked list with operations for insertion, deletion, and traversal.
- Q2. Write a program to reverse a linked list.
- Q3. Solve the "detect a cycle in a linked list" problem using Floyd’s Cycle Detection algorithm.
- Q4. Write a program to merge two sorted linked lists.
- Q5. Solve the "find the middle element of a linked list" problem.
Today's focus was on mastering the fundamentals of linked lists. I worked on implementing a singly linked list with essential operations like insertion, deletion, and traversal. Additionally, I solved problems such as reversing a linked list, detecting cycles using Floyd’s Cycle Detection algorithm, merging two sorted linked lists, and finding the middle element of a linked list. These exercises were instrumental in strengthening my foundation in linked list operations.
Check out my progress in my GitHub repository: github.com/AayJayTee/100-Days-DSA.
Q1. Implement a singly linked list with operations for insertion, deletion, and traversal.
#include <iostream>
using namespace std;
// Class representing a node in the linked list
class node {
public:
int data; // Data stored in the node
node* next; // Pointer to the next node
// Constructor to initialize a node with a value
node(int val) {
data = val;
next = NULL;
}
};
// Function to insert a node at the end of the linked list
void insertNodeatTail(node* &head, int val) {
node* n = new node(val); // Create a new node
if (head == NULL) { // If list is empty, make new node the head
head = n;
return;
}
node* temp = head; // Traverse to the end of the list
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = n; // Link the last node to the new node
}
// Function to insert a node at the beginning of the linked list
void insertNodeatHead(node* &head, int val) {
node* n = new node(val); // Create a new node
n->next = head; // Link the new node to the current head
head = n; // Update head to the new node
}
// Function to insert a node at a specific position
void insertNode(node* &head, int val, int pos) {
node* n = new node(val); // Create a new node
node* temp = head;
for (int i = 0; i < pos - 1; i++) { // Traverse to the desired position
temp = temp->next;
}
n->next = temp->next; // Link the new node to the next node
temp->next = n; // Link the previous node to the new node
}
// Function to delete a node from the end of the linked list
void deleteNodeatTail(node* &head) {
if (head == NULL) { // If the list is empty, do nothing
return;
}
if (head->next == NULL) { // If only one node exists
delete head; // Delete it and set head to NULL
head = NULL;
return;
}
node* temp = head; // Traverse to the second last node
while (temp->next->next != NULL) {
temp = temp->next;
}
node* to_delete = temp->next; // Save the last node
temp->next = NULL; // Unlink the last node
delete to_delete; // Delete the last node
}
// Function to delete a node from the beginning of the linked list
void deleteNodeatHead(node* &head) {
node* to_delete = head; // Save the current head
head = head->next; // Move head to the next node
delete to_delete; // Delete the old head
}
// Function to delete a node by value
void deleteNode(node* &head, int val) {
if (head == NULL) { // If the list is empty, do nothing
cout << "List is empty.\n";
return;
}
if (head->data == val) { // If the value is in the head node
deleteNodeatHead(head);
return;
}
node* temp = head;
while (temp->next->data != val) { // Traverse to the node before the target node
temp = temp->next;
}
if (temp->next == NULL) { // If the value is not found
cout << "Value not found.\n";
return;
}
node* to_delete = temp->next; // Save the target node
temp->next = temp->next->next; // Unlink the target node
delete to_delete; // Delete the target node
}
// Function to display the linked list
void display_linked_list(node* &head) {
cout<<"The linked list structure is: ";
node* temp = head;
while (temp != NULL) { // Traverse through the list
cout << temp->data << " "; // Print each node's data
temp = temp->next;
}
}
int main() {
node* head = NULL; // Initialize the linked list
insertNodeatTail(head, 1); // Insert nodes at the tail
insertNodeatTail(head, 2);
insertNodeatTail(head, 3);
display_linked_list(head); // Display the list
cout << endl;
insertNodeatHead(head, 4); // Insert a node at the head
display_linked_list(head);
cout << endl;
insertNode(head, 5, 3); // Insert a node at position 3
display_linked_list(head);
cout << endl;
deleteNode(head, 2); // Delete the node with value 2
display_linked_list(head);
cout << endl;
deleteNodeatHead(head); // Delete the head node
display_linked_list(head);
cout << endl;
deleteNodeatTail(head); // Delete the tail node
display_linked_list(head);
return 0;
}
The provided code implements a singly linked list with operations for insertion, deletion, and traversal. The node class represents a node in the linked list, storing an integer data and a pointer next to the subsequent node. The insertion functions include adding a node at the tail (insertNodeatTail), at the head (insertNodeatHead), and at a specific position (insertNode). The deletion functions allow removing a node at the head (deleteNodeatHead), at the tail (deleteNodeatTail), or by a specified value (deleteNode). The display_linked_list function traverses the list and prints the values of each node. The main function demonstrates these operations, starting with an empty list, adding nodes in different positions, removing nodes based on conditions, and displaying the linked list after each operation. This program effectively showcases the fundamental operations of a singly linked list and their implementation in C++.
Q2. Write a program to reverse a linked list.
#include <iostream>
using namespace std;
// Class representing a node in the linked list
class node {
public:
int data; // Data stored in the node
node* next; // Pointer to the next node
// Constructor to initialize a node with a value
node(int val) {
data = val;
next = NULL;
}
};
// Function to insert a node at the end of the linked list
void insertNodeatTail(node* &head, int val) {
node* n = new node(val); // Create a new node
if (head == NULL) { // If list is empty, make new node the head
head = n;
return;
}
node* temp = head; // Traverse to the end of the list
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = n; // Link the last node to the new node
}
// Function to display the linked list
void display_linked_list(node* &head) {
cout<<"The linked list structure is: ";
node* temp = head;
while (temp != NULL) { // Traverse through the list
cout << temp->data << " "; // Print each node's data
temp = temp->next;
}
}
void reverse_linked_list(node* &head){
node* prev_node = NULL; // Previous node pointer initialized to NULL
node* current_node = head; // Current node starts at the head
node* next_node; // Pointer to store the next node
while (current_node != NULL) {
next_node = current_node->next; // Store the next node
current_node->next = prev_node; // Reverse the current node's pointer
prev_node = current_node; // Move the previous pointer to the current node
current_node = next_node; // Move the current pointer to the next node
}
head = prev_node; // Update the head to the new first node
}
int main() {
node* head = NULL; // Initialize the linked list
insertNodeatTail(head, 1); // Insert nodes at the tail
insertNodeatTail(head, 2);
insertNodeatTail(head, 3);
insertNodeatTail(head, 4);
display_linked_list(head);
cout<<endl;
reverse_linked_list(head);
display_linked_list(head);
}
The code implements a singly linked list with functionality to reverse it. The node class represents a single node in the list, containing integer data and a pointer next. The insertNodeatTail function adds nodes at the end of the list, and display_linked_list traverses and prints the entire list. The reverse_linked_list function reverses the linked list iteratively. It uses three pointers: prev_node to track the previous node (initially NULL), current_node for the current node (starting at the head), and next_node to store the next node temporarily. By iterating through the list, it reverses the direction of each node's next pointer and updates the head to the last node after traversal. The main function demonstrates this functionality by creating a linked list, displaying it, reversing it, and displaying the reversed list.
Q3. Solve the "detect a cycle in a linked list" problem using Floyd’s Cycle Detection algorithm.
#include <iostream>
using namespace std;
// Class representing a node in the linked list
class node {
public:
int data; // Data stored in the node
node* next; // Pointer to the next node
// Constructor to initialize a node with a value
node(int val) {
data = val;
next = NULL;
}
};
// Function to insert a node at the end of the linked list
void insertNodeatTail(node* &head, int val) {
node* n = new node(val); // Create a new node
if (head == NULL) { // If list is empty, make new node the head
head = n;
return;
}
node* temp = head; // Traverse to the end of the list
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = n; // Link the last node to the new node
}
// Function to display the linked list
void display_linked_list(node* &head) {
cout<<"The linked list structure is: ";
node* temp = head;
while (temp != NULL) { // Traverse through the list
cout << temp->data << " "; // Print each node's data
temp = temp->next;
}
}
//Function to detect if cycle is present
bool isCyclePresent(node* &head){
node* fast = head; // Fast pointer starts at the head
node* slow = head; // Slow pointer starts at the head
while(fast != NULL && fast->next != NULL){ // Loop until fast pointer reaches the end
fast = fast->next->next; // Move fast pointer two steps ahead
slow = slow->next; // Move slow pointer one step ahead
if(fast == slow){ // If they meet, a cycle is present
return true;
}
}
return false; // No cycle found
}
// Function to create a cycle in the linked list for testing
void createCycle(node* &head) {
if (head == NULL) return;
node* temp = head;
while (temp->next != NULL) {
temp = temp->next; // Traverse to the last node
}
// Create a cycle by linking the last node to a node (e.g., the second node)
temp->next = head->next; // Create a cycle by making the last node point to the second node
}
int main() {
node* head = NULL; // Initialize the linked list
insertNodeatTail(head, 1); // Insert nodes at the tail
insertNodeatTail(head, 2);
insertNodeatTail(head, 3);
insertNodeatTail(head, 4);
display_linked_list(head);
cout<<endl;
if(isCyclePresent(head)){
cout<<"Cycle is present";
}
else{
cout<<"Cycle is not present";
}
createCycle(head);
cout<<endl;
cout<<"Cycle has been created";
cout<<endl;
if(isCyclePresent(head)){ //Using the function to create a cycle
cout<<"Cycle is present";
}
else
cout<<"Cycle is not present";
}
The program demonstrates how to work with a singly linked list, including functionality to detect and create cycles. The node class represents each element of the list, containing data and a pointer to the next node. The insertNodeatTail function appends nodes to the list, and display_linked_list prints the elements in order.
The isCyclePresent function detects whether a cycle exists in the list using the Floyd’s Cycle Detection Algorithm (tortoise and hare approach). Two pointers, slow and fast, traverse the list at different speeds. If they meet, a cycle exists; otherwise, the traversal ends when fast reaches NULL.
The createCycle function artificially creates a cycle by linking the last node to a middle node. In main, a list is constructed, displayed, and tested for cycles. Initially, no cycle exists. After invoking createCycle, a cycle is created, and the program verifies its presence using isCyclePresent. The output illustrates both scenarios, demonstrating the linked list operations and cycle detection effectively.
Q4. Write a program to merge two sorted linked lists.
#include <iostream>
using namespace std;
// Class representing a node in the linked list
class node {
public:
int data; // Data stored in the node
node* next; // Pointer to the next node
// Constructor to initialize a node with a value
node(int val) {
data = val;
next = NULL;
}
};
// Function to insert a node at the end of the linked list
void insertNodeatTail(node* &head, int val) {
node* n = new node(val); // Create a new node
if (head == NULL) { // If list is empty, make new node the head
head = n;
return;
}
node* temp = head; // Traverse to the end of the list
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = n; // Link the last node to the new node
}
// Function to display the linked list
void display_linked_list(node* &head) {
cout<<"The linked list structure is: ";
node* temp = head;
while (temp != NULL) { // Traverse through the list
cout << temp->data << " "; // Print each node's data
temp = temp->next;
}
}
void merge_linked_lists(node* &head1, node* &head2) {
// If the first list is empty, point it to the second list
if (head1 == NULL) {
head1 = head2;
}
// If the second list is empty, there's nothing to merge, so return
if (head2 == NULL) {
return;
}
// Traverse to the end of the first linked list
node* temp = head1;
while (temp->next != NULL) {
temp = temp->next;
}
// Link the last node of the first list to the head of the second list
temp->next = head2;
}
int main() {
node* head1 = NULL; // Initialize the linked list
insertNodeatTail(head1, 1); // Insert nodes at the tail
insertNodeatTail(head1, 2);
insertNodeatTail(head1, 3);
insertNodeatTail(head1, 4);
display_linked_list(head1);
cout<<endl;
node* head2 = NULL;
insertNodeatTail(head2, 5); // Insert nodes at the tail
insertNodeatTail(head2, 6);
insertNodeatTail(head2, 7);
insertNodeatTail(head2, 8);
display_linked_list(head2);
cout<<endl;
merge_linked_lists(head1,head2);
display_linked_list(head1);
}
This program demonstrates the creation, traversal, and merging of two singly linked lists. A class node is defined to represent each node in the linked list, storing data and a pointer to the next node. The insertNodeatTail function inserts a new node with a given value at the end of the linked list. The display_linked_list function traverses the list, printing the data in each node.
The merge_linked_lists function combines two linked lists. If the first list (head1) is empty, it points to the second list (head2). If the second list is empty, no changes are made. Otherwise, the function traverses to the last node of the first list and links it to the head of the second list, effectively merging the two lists.
In the main function, two linked lists (head1 and head2) are created and populated with nodes using insertNodeatTail. Both lists are displayed individually using display_linked_list. Then, merge_linked_lists is called to merge the two lists, and the resulting merged list is displayed.
Q5. Solve the "find the middle element of a linked list" problem.
#include <iostream>
using namespace std;
// Class representing a node in the linked list
class node {
public:
int data; // Data stored in the node
node* next; // Pointer to the next node
// Constructor to initialize a node with a value
node(int val) {
data = val;
next = NULL;
}
};
// Function to insert a node at the end of the linked list
void insertNodeatTail(node* &head, int val) {
node* n = new node(val); // Create a new node
if (head == NULL) { // If list is empty, make new node the head
head = n;
return;
}
node* temp = head; // Traverse to the end of the list
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = n; // Link the last node to the new node
}
void findMiddle(node* &head){
node* fast=head;
node* slow=head;
while(fast!=NULL && fast->next!=NULL){
fast=fast->next->next;
slow=slow->next;
}
cout<<"The middle element is: ";
cout<<slow->data;
}
// Function to display the linked list
void display_linked_list(node* &head) {
cout<<"The linked list structure is: ";
node* temp = head;
while (temp != NULL) { // Traverse through the list
cout << temp->data << " "; // Print each node's data
temp = temp->next;
}
}
int main() {
node* head = NULL; // Initialize the linked list
insertNodeatTail(head, 1); // Insert nodes at the tail
insertNodeatTail(head, 2);
insertNodeatTail(head, 3);
insertNodeatTail(head, 4);
insertNodeatTail(head, 5);
insertNodeatTail(head, 6);
insertNodeatTail(head, 7);
display_linked_list(head);
cout<<endl;
findMiddle(head);
}
This program identifies the middle element of a singly linked list. The class node represents each node in the linked list, with properties for storing data and pointing to the next node. The insertNodeatTail function appends a new node with a given value to the end of the list, while the display_linked_list function traverses and prints all elements of the list.
The findMiddle function determines the middle element using the two-pointer approach. It initializes two pointers: slow (which moves one step at a time) and fast (which moves two steps at a time). When the fast pointer reaches the end of the list, the slow pointer will be at the middle element. The value of the middle node is then printed.
In the main function, a linked list is created and populated with seven nodes using insertNodeatTail. The list is displayed using display_linked_list. The findMiddle function is then called to calculate and display the middle element of the list.
Today's practice significantly enhanced my understanding of linked lists. Implementing core operations, detecting cycles, and solving practical problems like merging sorted lists and finding the middle element provided a comprehensive learning experience. Excited to delve deeper into more advanced linked list problems in the coming days. Onward to Day 11!