Skip to main content

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




Comment

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