Doubly Linked List in C++ (Part 1)
Data Structure Series
Same or not
Take two doubly linked lists as input and check if they are the same or not.
Sample Input
10 20 30 40 50 -1
10 20 30 40 50 -1
Sample Output
YES
Sample Input
10 20 30 40 50 -1
10 20 30 40 -1
Sample Output
NO
Sample Input
10 20 30 40 -1
10 20 30 40 50 -1
Sample Output
NO
Sample Input
10 20 30 40 -1
40 30 20 10 -1
Sample Output
NO
Sample Input
1 2 3 4 5 -1
5 4 1 2 6 -1
Sample Output
NO
Try on your own first.
Answer:
#include<bits/stdc++.h>
using namespace std;
// Node structure for each element in the doubly linked list
class Node {
int data;
Node* prev;
Node* next;
// Constructor to create a new node with a value
Node(int val) {
data = val;
prev = nullptr;
next = nullptr;
}
};
// Class for the doubly linked list
class DoublyLinkedList {
public:
Node* head;
Node* tail;
// Constructor to initialize an empty doubly linked list
DoublyLinkedList() {
head = nullptr;
tail = nullptr;
}
// Function to insert a new node at the end of the list
void insert(int value) {
Node* newNode = new Node(value);
if (head == nullptr) {
head = tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
}
// Function to check if two lists are identical
bool isIdentical(DoublyLinkedList& other) {
Node* temp1 = head;
Node* temp2 = other.head;
// Traverse both lists and compare data
while (temp1 != nullptr && temp2 != nullptr) {
if (temp1->data != temp2->data) {
return false;
}
temp1 = temp1->next;
temp2 = temp2->next;
}
// Check if both lists reached the end
return (temp1 == nullptr && temp2 == nullptr);
}
};
int main() {
DoublyLinkedList list1, list2;
int value;
// Input the first list until -1 is encountered
while (cin >> value && value != -1) {
list1.insert(value);
}
// Input the second list until -1 is encountered
while (cin >> value && value != -1) {
list2.insert(value);
}
// Check if the lists are identical and print the result
if (list1.isIdentical(list2)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
return 0;
}Reverse
Take a doubly linked list as input and reverse it. After that print the linked list.
Sample Input
10 20 30 -1
Sample Output
30 20 10
Sample Input
10 20 30 40 -1
Sample Output
40 30 20 10
Try on your own first.
Answer:
#include<bits/stdc++.h>
using namespace std;
class Node {
public:
int val;
Node* next;
Node* prev;
Node(int val) {
this->val = val;
this->next = NULL;
this->prev = NULL;
}
};
void print_list(Node* head) {
Node* tmp = head;
while (tmp != NULL) {
cout << tmp->val << " ";
tmp = tmp->next;
}
cout << endl;
}
void reverse(Node*&head, Node*&tail){
if(head==NULL || head->next==NULL){
return;
}
Node*i=head;
Node*j=tail;
while(i!=j && i->prev!=j){
swap(i->val, j->val);
i=i->next;
j=j->prev;
}
}
int main() {
Node* head = NULL;
Node* tail = NULL;
int val;
while (true) {
cin >> val;
if (val == -1) break;
Node* newNode = new Node(val);
if (head == NULL) {
head = newNode;
tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
}
reverse(head, tail);
print_list(head);
return 0;
}Palindrome
Take a doubly linked list as input and check if it forms any palindrome or not.
Sample Input
10 20 30 20 10 -1
Sample Output
YES
Sample Input
10 20 30 30 20 10 -1
Sample Output
YES
Sample Input
10 20 30 40 20 10 -1
Sample Output
NO
Sample Input
10 20 30 20 40 -1
Sample Output
NO
Sample Input
10 20 30 10 10 -1
Sample Output
NO
Sample Input
10 20 20 20 10 -1
Sample Output
YES
Try on your own first.
Answer:
#include<bits/stdc++.h>
using namespace std;
class Node {
public:
int val;
Node* next;
Node* prev;
Node(int val) {
this->val = val;
this->next = NULL;
this->prev = NULL;
}
};
bool is_palindrome(Node*head){
if(head==NULL || head->next==NULL){
return true;
}
Node*start=head;
Node*end=head;
while(end->next!=NULL){
end=end->next;
}
while(start!=NULL){
if(start->val!=end->val){
return false;
}
start=start->next;
end=end->prev;
}
return true;
}
int main(){
Node*head =NULL;
Node*tail =NULL;
int val;
while(true) {
cin>>val;
if(val==-1) break;
Node* newNode =new Node(val);
if(head==NULL) {
head=newNode;
tail=newNode;
}
else{
tail->next=newNode;
newNode->prev =tail;
tail=newNode;
}
}
if(is_palindrome(head)){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
return 0;
}Order (Ascending)
Take a doubly linked list as input and sort it in ascending order. Then print the list.
Sample Input
1 4 5 2 7 -1
Sample Output
1 2 4 5 7
Sample Input
20 40 30 10 50 60 -1
Sample Output
10 20 30 40 50 60
Try on your own first.
Answer:
#include<bits/stdc++.h>
using namespace std;
int main (){
list<int> myList;
int val;
while (true) {
cin >> val;
if (val == -1) break;
myList.push_back(val);
}
myList.sort();
for(int val:myList){
cout<<val<<" ";
}
cout<<endl;
return 0;
}Order (Descending)
Take a doubly linked list as input and sort it in ascending order. Then print the list.
Sample Input
10 20 30 40 20 10 -1
Sample Output
40 30 20 20 10 10
Sample Input
20 40 30 10 50 60 -1
Sample Output
60 50 40 30 20 10
Try on your own first.
Answer:
#include <bits/stdc++.h>
using namespace std;
int main() {
list<int> myList;
int val;
// Take input until -1 is encountered
while (true) {
cin >> val;
if (val == -1) break;
myList.push_back(val);
}
// Sort the list in descending order
myList.sort(greater<int>());
// Print the sorted list
for (int val : myList) {
cout << val << " ";
}
cout << endl;
return 0;
}Please Clap, Share, and Follow. It means a LOT!!!
