Alternating split of singly linked list in c++
C++ program for Alternating split of singly linked list. Here problem description and explanation.
// Include header file
#include <iostream>
using namespace std;
// C++ program for
// Alternating split of a given singly linked list
// Node of LinkedList
class LinkNode
{
public: int data;
LinkNode *next;
LinkNode(int data)
{
// Set node value
this->data = data;
this->next = nullptr;
}
};
class MyLinkedList
{
public: LinkNode *head;
MyLinkedList()
{
this->head = nullptr;
}
// Add new node at the end of linked list
void insert(int value)
{
// Create a new node
LinkNode *node = new LinkNode(value);
if (this->head == nullptr)
{
this->head = node;
}
else
{
LinkNode *temp = this->head;
// Find last node
while (temp->next != nullptr)
{
// Visit to next node
temp = temp->next;
}
// Add node at last position
temp->next = node;
}
}
// Display all Linked List elements
void display()
{
if (this->head != nullptr)
{
LinkNode *temp = this->head;
while (temp != nullptr)
{
// Display node value
cout << " " << temp->data;
// Visit to next node
temp = temp->next;
}
}
else
{
cout << "Empty Linked list" << endl;
}
}
// Split the linked list by alternating nodes
LinkNode *splitting()
{
LinkNode *result = nullptr;
if (this->head != nullptr)
{
// Some auxiliary variables
LinkNode *temp = this->head;
LinkNode *tail = nullptr;
LinkNode *current = nullptr;
LinkNode *prev = this->head;
while (temp != nullptr &&
temp->next != nullptr)
{
current = temp->next;
prev = temp;
temp = temp->next->next;
if (result == nullptr)
{
// When first node of second linked list
current->next = result;
result = current;
tail = current;
}
else
{
// Add Alternating node to end of
// second linked list
current->next = tail->next;
tail->next = current;
tail = current;
}
prev->next = temp;
}
}
return result;
}
};
int main()
{
MyLinkedList *l1 = new MyLinkedList();
MyLinkedList *l2 = new MyLinkedList();
// Add node in l1 linked list
l1->insert(1);
l1->insert(2);
l1->insert(3);
l1->insert(4);
l1->insert(5);
l1->insert(6);
l1->insert(7);
l1->insert(8);
// Before splitting l1
cout << "L1 list : ";
l1->display();
l2->head = l1->splitting();
cout << "\nAfter splitting " << endl;
cout << "L1 list : ";
l1->display();
cout << "\nL2 list : ";
l2->display();
return 0;
}
Output
L1 list : 1 2 3 4 5 6 7 8
After splitting
L1 list : 1 3 5 7
L2 list : 2 4 6 8
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