Alternating split of a Singly Linked List

Intuition

The most basic method iterates over 'List,' pulling nodes from the 'List' and placing them at the front (or beginning) of 'List1' and 'List2' alternatively. The only weird thing is that the nodes will appear in 'List' in reverse order. Method 2 keeps track of the last node in sublists and inserts the node at the end.

Code

#include <bits/stdc++.h>
using namespace std;


// Node class.
class Node
{
public: 
int value;
Node *next;
Node(int value)
{
// Constructor
this->value = value;
this->next = NULL;
}
};
class MyList
{
public:
Node *head;
MyList()
{
this->head = NULL;
}
// For adding node.
void insert(int value)
{
// New node
Node *node = new Node(value);
if (this->head == NULL)
{
this->head = node;
}
else
{
Node *temp = this->head;

// Adding
while (temp->next != nullptr)
{
// Next node 
temp = temp->next;
}
// Added
temp->next = node;
}
}
// Display all Linked List elements
void display()
{
if (this->head != NULL)
{
Node *temp = this->head;
while (temp != NULL)
{
cout << "  " << temp->value;
temp = temp->next;
}
}
else
{
cout << "Empty Linked list" << endl;
}
}
// Splitting
Node *splitting()
{
Node *result = NULL;
if (head != NULL)
{
// Temporary Variables.
Node *temp = head;
Node *tail = NULL;
Node *current = NULL;
Node *prev = head;
while (temp != NULL && 
                   temp->next != NULL)
{
current = temp->next;
prev = temp;
temp = temp->next->next;
if (result == nullptr)
{
current->next = result;
result = current;
tail = current;
}
else
{
// Adding alternate nodes to end of second list.
current->next = tail->next;
tail->next = current;
tail = current;
}
prev->next = temp;
}
}
return result;
}
};
int main()
{
MyList *l1 = new MyList();
MyList *l2 = new MyList();

// Adding nodes to l1 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
cout << "List: ";
l1->display();
l2->head = l1->splitting();
cout << "\nAfter" << endl;
cout << "List1 : ";
l1->display();
cout << "\nList2 : ";
l2->display();
return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

List:   1  2  3  4  5  6  7  8
After
List1 :   1  3  5  7
List2 :   2  4  6  8

Time Complexity

O(N), where ‘N’ stands for length of the linked list.

Reason- We are traversing over the list only once.

Space Complexity

O(1)

Reason- No extra space used.

Check out this problem - Reverse Nodes In K Group

Frequently asked questions

What is a linked list?

Collection of data in linear form in which order is not determined by their actual location in memory in computer science. Rather, each part is linked to the next. It's a data structure made up of a series of nodes that collectively represent a sequence.

What are the advantages of a linked list?

1. A linked list is a dynamic data structure that can expand and contract in size by allocating and deallocating memory at runtime. As a result, the starting size of the linked list does not need to be specified.
2. Because the size of the linked list rises or decreases at runtime, there is no memory waste and no need to pre-allocate memory.

What are the disadvantages of a linked list? 

1. An array uses less memory than a linked list. A pointer requires additional memory since it is required to store the address of the next element in a linked list.
2. It takes longer to traverse a linked list than it does to traverse an array. Unlike an array by index, a linked list does not provide direct access to an entry. To get to a mode at position n, for example, you must traverse all nodes before it.

What is the purpose of linked list?

Arrays can be used to store similar types of linear data, but we must know the maximum number of elements ahead of time because the array size is fixed. Furthermore, the allotted RAM is always equal to the upper limit, regardless of consumption.

Is there anything else in Coding Ninjas Studio about Data Structures and Algorithms?

Yes, you may use Coding Ninjas Studio to practise coding while also answering common interview questions. More you practice, more you have an edge of getting a job in your dream company.

Conclusion

The 'Alternating split of a Singly Linked List' has been fully covered in this article. We hope that this blog has improved your understanding of 'Linked Lists.' If you'd like to learn more, visit our Library, where you'll find everything you need to know about your preparation, including a Complete course,  Interview Experiences, and other guided paths.. Please upvote our blog to assist other ninjas in their development. Good luck with your coding!