## Introduction

One of the most essential subjects for technical interviews at product-based companies is linked lists. In companies like Google, Microsoft, Facebook, Amazon, and Flipkart, questions from the linked list are frequently asked. It is critical to have a thorough understanding of this subject.

In this blog, we will discuss a problem based on Linked Lists in detail. We will discuss multiple approaches to solve the problem along with their time and space complexity details.

Recommended Topic, __Floyds Algorithm__ And __Rabin Karp Algorithm__

### Problem Statement

Ninja has given you a Linked List and a key. Your task is to move all occurrences of the key element in the Linked List at the end of it without changing the order of the rest of the elements.

### Sample Examples

**Input**

```
Enter the number of elements in the Linked List: 10
Enter the elements in the Linked List: 9 3 4 3 5 6 3 2 3 1
Key: 3
```

**Output**

```
Output Linked List
9 -> 4 -> 5 -> 6 -> 2 -> 1 -> 3 -> 3 -> 3 -> 3
```

**Explanation**

All the four occurrences of the nodes with key = 3 have been moved to the end.

**Input**

```
Enter the number of elements in the Linked List: 4
Enter the elements in the Linked List: 1 2 1 3
Key: 1
```

**Output**

```
Output Linked List
2 -> 3 -> 1 -> 1
```

**Explanation**

All two occurrences of the nodes with key = 1 have been moved to the end.

## Brute Force Approach

The most straightforward approach is to create a new linked list with the required properties. For this, we can count the number of elements with a value equal to the given key and store it in a variable, say countKey. Now, we can iterate through the given linked list and add a node to the new linked list if the value of the node in the given linked list is not equal to the given key. Finally, we can add countKey number of nodes in the new linked list with value equal to key.

### Algorithm

- Iterate through the given Linked List and count the number of nodes with value = key and store it in countKey.
- Create an empty Linked List, say outputLinkedList.
- Iterate through the given Linked List and for each node, if its value is not equal to key, create a new node at the end of outputLinkedList with the same value.
- Finally, add countKey number of nodes at the end of outputLinkedList with value = key.

### Implementation in C++

```
#include <bits/stdc++.h>
using namespace std;
// Individual nodes of Linked Lists
struct Node
{
int val;
struct Node *next;
};
// Function to create a new node of the linked list.
Node *newNode(int data)
{
struct Node *node = new Node();
// Populate the node with the provided data.
node->val = data;
node->next = NULL;
// Return the node.
return node;
}
// Function to print a linked list.
void printLL(Node *root)
{
while (root != NULL)
{
if (root->next == NULL)
break;
// Print the value of the node.
cout << root->val << " -> ";
root = root->next;
}
if (root != NULL)
{
cout << root->val << endl;
}
}
// Function to insert a node at the end of a linked list.
Node *addNodeAtEnd(Node *endPointer, int val)
{
// Create the node.
Node *node = newNode(val);
// If the list is empty.
if (endPointer == NULL)
{
endPointer = node;
return endPointer;
}
// If not, insert at the end and update the end pointer.
endPointer->next = node;
endPointer = endPointer->next;
return endPointer;
}
// Function to find the solution.
void traverseLL(Node *root, int key)
{
// Root of the output Linked list.
Node *newRoot = NULL;
Node *endPointer = NULL;
// To count the number of nodes with val = key.
int countKey = 0;
while (root)
{
// As discussed in the approach.
if (root->val == key)
{
countKey++;
}
else
{
// Add the current node at the end of the output linked list.
endPointer = addNodeAtEnd(endPointer, root->val);
if (newRoot == NULL)
{
newRoot = endPointer;
}
}
// Move to the next node.
root = root->next;
}
while (countKey > 0)
{
// Add countKey number of nodes at the end of output Linked list.
endPointer = addNodeAtEnd(endPointer, key);
if (newRoot == NULL)
{
newRoot = endPointer;
}
countKey--;
}
// Print the Output.
printLL(newRoot);
}
int main()
{
// Take the input.
cout << "Enter the number of elements in the Linked List: ";
// Take the size of the input linked list.
int size;
cin >> size;
// Take the individual nodes of a linked list.
cout << "Enter the elements in the Linked List (space separated): ";
Node *root = NULL;
Node *endP = NULL;
// Take the linked list as input.
for (int i = 0; i < size; i++)
{
int val;
cin >> val;
// Add the current node at the end of the input linked list.
// Update the root if it is null.
endP = addNodeAtEnd(endP, val);
if (root == NULL)
root = endP;
}
// Take the key.
cout << "Enter the key: ";
int key;
cin >> key;
// Find the solution.
traverseLL(root, key);
}
```

**Input**

```
Enter the number of elements in the Linked List: 4
Enter the elements in the Linked List: 1 2 1 3
Key: 1
```

**Output**

```
Output Linked List
2 -> 3 -> 1 -> 1
```

#### Time Complexity Analysis

Time complexity of the above approach is O(N), where N is the number of elements in the Linked List.

It is because we are iterating through the input Linked List twice.

#### Space Complexity Analysis

Space Complexity of the above approach is O(N), where N is the number of elements in the Linked List.

It is because we are creating a new linked list with a number of nodes equal to N.