Data Structure in C++: Single Linked List (Part-1)
Question 1:
Take a single linked list as input and print the size of the linked list.
Sample Input
2 1 5 3 4 8 9 -1
Sample Output
7
Sample Input
5 1 4 5 -1
Sample Output
4
Try on your own first.
Answer:
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int val;
Node* next;
Node(int val) {
this->val = val;
this->next = NULL;
}
};
// Function to calculate the size of the linked list
int getSize(Node* head) {
int size = 0;
Node* current = head;
while (current != NULL) {
size++;
current = current->next;
}
return size;
}
int main() {
Node* head = NULL;
Node* tail = NULL;
int val;
// Inputting values into the linked list
while (cin >> val && val != -1) {
Node* new_node = new Node(val);
if (head == NULL) {
head = tail = new_node;
} else {
tail->next = new_node;
tail = new_node;
}
}
// Print the size of the linked list
cout << getSize(head) << endl;
return 0;
}Question 2: Take a single linked list as input and check if the linked list contains any duplicate value. You can assume that the maximum value will be 100.
Sample Input
5 4 8 6 2 1 -1
Sample Output
NO
Sample Input
2 4 5 6 7 4 -1
Sample Output
YES
Try on your own:
Answer:
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int val;
Node* next;
Node(int val) {
this->val = val;
this->next = NULL;
}
};
// Function to check for duplicates in the linked list
bool hasDuplicate(Node* head) {
bool seen[101] = {false}; // Array to track seen values (0 to 100)
Node* current = head;
while (current != NULL) {
if (seen[current->val]) {
return true; // Duplicate found
}
seen[current->val] = true;
current = current->next;
}
return false; // No duplicates
}
int main() {
Node* head = NULL;
Node* tail = NULL;
int val;
// Inputting values into the linked list
while (cin >> val && val != -1) {
Node* new_node = new Node(val);
if (head == NULL) {
head = tail = new_node;
} else {
tail->next = new_node;
tail = new_node;
}
}
// Check for duplicates and print the result
if (hasDuplicate(head)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
return 0;
}Question 3: Take a singly linked list as input and print the middle element. If there are multiple values in the middle print both.
Sample Input
2 4 6 8 10 -1
Sample Output
6
Sample Input
1 2 3 4 5 6 -1
Sample Output
3 4
Sample Input
2 1 5 3 4 8 9 8 -1
Sample Output
3 4
Try on your own first.
Answer:
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int val;
Node* next;
Node(int val) {
this->val = val;
this->next = NULL;
}
};
// Function to find and print the middle element(s) of the linked list
void printMiddle(Node* head) {
if (head == NULL) {
return;
}
Node* slow = head;
Node* fast = head;
// Use two pointers: slow moves one step, fast moves two steps
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
// If the total number of nodes is even, print the two middle elements
if (fast == NULL) {
Node* midPrev = head;
while (midPrev->next != slow) {
midPrev = midPrev->next;
}
cout << midPrev->val << " " << slow->val << endl;
} else {
// If the total number of nodes is odd, print the single middle element
cout << slow->val << endl;
}
}
int main() {
Node* head = NULL;
Node* tail = NULL;
int val;
// Inputting values into the linked list
while (cin >> val && val != -1) {
Node* new_node = new Node(val);
if (head == NULL) {
head = tail = new_node;
} else {
tail->next = new_node;
tail = new_node;
}
}
// Print the middle element(s)
printMiddle(head);
return 0;
}Question 4: Take a singly linked list as input and check if the linked list is sorted in ascending order.
Sample Input
1 5 6 8 9 -1
Sample Output
YES
Sample Input
2 4 6 5 8 4 -1
Sample Output
NO
Try on your own first.
Answer:
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int val;
Node* next;
Node(int val) {
this->val = val;
this->next = NULL;
}
};
// Function to check if the linked list is sorted in ascending order
bool isSorted(Node* head) {
Node* current = head;
while (current != NULL && current->next != NULL) {
if (current->val > current->next->val) {
return false; // Not sorted
}
current = current->next;
}
return true; // Sorted
}
int main() {
Node* head = NULL;
Node* tail = NULL;
int val;
// Inputting values into the linked list
while (cin >> val && val != -1) {
Node* new_node = new Node(val);
if (head == NULL) {
head = tail = new_node;
} else {
tail->next = new_node;
tail = new_node;
}
}
// Check if the linked list is sorted and print the result
if (isSorted(head)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
return 0;
}Hardest Question 5: Take a singly linked list as input, then take q queries. In each query, you will be given an index and value. You need to insert those values in the given index and print the linked list. If the index is invalid print “Invalid”.
Sample Input
10 20 30 -1
1 40
5 50
4 50
0 100
7 40
1 110
7 40
Sample Output
10 40 20 30
Invalid
10 40 20 30 50
100 10 40 20 30 50
Invalid
100 110 10 40 20 30 50
100 110 10 40 20 30 50 40
Try on your own.
Answer:
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int val;
Node* next;
Node(int val) {
this->val = val;
this->next = NULL;
}
};
// Function to print the linked list
void print_linked_list(Node* head) {
Node* current = head;
while (current != NULL) {
cout << current->val << " ";
current = current->next;
}
cout << endl;
}
// Function to insert a value at a specific index in the linked list
void insertAtIndex(Node*& head, int index, int value) {
Node* new_node = new Node(value);
if (index == 0) {
new_node->next = head;
head = new_node;
print_linked_list(head);
return;
}
Node* current = head;
for (int i = 0; i < index - 1 && current != NULL; i++) {
current = current->next;
}
if (current == NULL) {
cout << "Invalid" << endl;
delete new_node;
return;
}
new_node->next = current->next;
current->next = new_node;
print_linked_list(head);
}
int main() {
Node* head = NULL;
Node* tail = NULL;
int val;
// Inputting values into the linked list
while (cin >> val && val != -1) {
Node* new_node = new Node(val);
if (head == NULL) {
head = tail = new_node;
} else {
tail->next = new_node;
tail = new_node;
}
}
int index, value;
// Reading and handling queries
while (cin >> index >> value) {
insertAtIndex(head, index, value);
}
return 0;
}Please Clap, Share, and Follow.
