1.
Introduction
2.
Problem Statement
2.1.
Input
2.2.
Output
2.3.
Explanation
3.
Intuition
3.1.
Code
3.1.1.
Output
3.1.2.
Time Complexity
3.1.3.
Space Complexity
4.
4.1.
4.2.
4.3.
4.4.
What is the purpose of linked list?
4.5.
Is there anything else in Coding Ninjas Studio about Data Structures and Algorithms?
5.
Conclusion
Last Updated: Mar 27, 2024

# Alternating split of a Singly Linked List

Saksham Gupta
0 upvote

## Introduction

Any coding interview is built on the foundation of linked lists. As a result, having a firm handle on the Linked list is critical. But don't be concerned about anything. Ninjas are here to help, and today we'll talk about "Alternating split of a Singly Linked List."

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm.

## Problem Statement

We have been given a linked list â€˜Listâ€™, our task is to create two smaller linked lists â€˜List1â€™ and â€˜List2â€™ from â€˜Listâ€™ with alternating nodes. The following example will give you a better understanding of the problem.

(List1)

(List2)

### Explanation

We can see that List1 and List contain alternative nodes

## 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:
MyList()
{
}
void insert(int value)
{
// New node
Node *node = new Node(value);
{
}
else
{

while (temp->next != nullptr)
{
// Next node
temp = temp->next;
}
temp->next = node;
}
}
// Display all Linked List elements
void display()
{
{
while (temp != NULL)
{
cout << "  " << temp->value;
temp = temp->next;
}
}
else
{
cout << "Empty Linked list" << endl;
}
}
// Splitting
Node *splitting()
{
Node *result = NULL;
{
// Temporary Variables.
Node *tail = NULL;
Node *current = NULL;
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();
cout << "\nAfter" << endl;
cout << "List1 : ";
l1->display();
cout << "\nList2 : ";
l2->display();
return 0;
}``````

#### 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

### 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.

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.

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.