Flatten a folded linked list in c++
C++ program for Flatten a folded linked list. Here problem description and explanation.
// Include header file
#include <iostream>
using namespace std;
/*
C++ program for
Unfold a folded linked list OR
flatten folded linked list
*/
// Linked list node
class LinkNode
{
public: int data;
LinkNode *next;
LinkNode(int data)
{
this->data = data;
this->next = nullptr;
}
};
class SingleLL
{
public: LinkNode *head;
SingleLL()
{
this->head = nullptr;
}
// Insert node at the beginning of linked list
void addNode(int data)
{
// Create node
LinkNode *node = new LinkNode(data);
node->next = this->head;
// Set new head
this->head = node;
}
// Display linked list element
void display()
{
if (this->head == nullptr)
{
return;
}
LinkNode *temp = this->head;
// iterating linked list elements
while (temp != nullptr)
{
cout << " " << temp->data << " →";
// Visit to next node
temp = temp->next;
}
cout << " NULL" << endl;
}
// This is handle the request of unfold given linked list nodes
void unfoldList()
{
if (this->head == nullptr)
{
cout << "\n Empty linked list" << endl;
return;
}
LinkNode *temp = this->head;
LinkNode *auxiliary = nullptr;
LinkNode *hold = nullptr;
// Loop which is separating the fold elements
while (temp->next != nullptr)
{
// Get the second element
hold = temp->next;
if (hold->next != nullptr)
{
// When exists pair of three elements
temp->next = hold->next;
// Visit to 3rd element
temp = hold->next;
}
else
{
// When get last two elements
temp->next = nullptr;
}
// Add new node at beginning of auxiliary linked list
hold->next = auxiliary;
// Make new head node
auxiliary = hold;
}
if (temp != nullptr)
{
// Combine lists
temp->next = auxiliary;
}
}
};
int main()
{
// Create a empty linked lists
SingleLL *sll1 = new SingleLL();
SingleLL *sll2 = new SingleLL();
// Constructed first linked list
// 2 → 5 → 1 → 8 → 10 → 4 → 9 → 7 → NULL
sll1->addNode(7);
sll1->addNode(9);
sll1->addNode(4);
sll1->addNode(10);
sll1->addNode(8);
sll1->addNode(1);
sll1->addNode(5);
sll1->addNode(2);
// Constructed second linked list
// 1 → 2 → 3 → 4 → 5 → 6 → 7 → NULL
sll2->addNode(7);
sll2->addNode(6);
sll2->addNode(5);
sll2->addNode(4);
sll2->addNode(3);
sll2->addNode(2);
sll2->addNode(1);
// Test A
cout << " Before unfold" << endl;
sll1->display();
sll1->unfoldList();
cout << " After unfold" << endl;
sll1->display();
// Test B
cout << " Before unfold" << endl;
sll2->display();
sll2->unfoldList();
cout << " After unfold" << endl;
sll2->display();
return 0;
}
Output
Before unfold
2 → 5 → 1 → 8 → 10 → 4 → 9 → 7 → NULL
After unfold
2 → 1 → 10 → 9 → 7 → 4 → 8 → 5 → NULL
Before unfold
1 → 2 → 3 → 4 → 5 → 6 → 7 → NULL
After unfold
1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment