Get this book -> Problems on Array: For Interviews and Competitive Programming

In this problem, given a linked list and an input key value, the task is to move all occurrences of the given key to the end of the linked list.

```
Example input:
1 -> 2 -> 2 -> 3
Key value: 2
Example output:
1 -> 3 -> 2 -> 2
```

### What are linked lists ?

Linked List is a data structure. It is a linear data structure where the elements of the linked list are stored in non-consecutive

memory locations, each node in the linked list contains a data item and pointer to the next node in the linked list.

### Representation of linked lists

In our program we have represented a linked list using a `struct`

construct in C++.

```
struct node {
int data;
struct node* next;
};
```

Here, `data`

represents the data value in the node and the `next`

pointer represents the pointer to the next node in the list.

# Brute Force Solution Approach

In this approach we find every occurrence of the given key element. For each occurrence of the given key element, it is moved to the end of the linked list.

**Time complexity**: The worst case complexity of this brute force approach is given by O(N * N), where N is the number of nodes in the linked list.

As we take for each element O(N) time to traverse the linked list and find the element to append it.

# Efficient Solution Approach

This approach we maintain two pointers, the current pointer and the tail pointer, the head pointer traverses the linked list, whenever an instance of the key is found, the links are updated and a node is inserted at the end of linked list using the tail pointer.

```
#include <bits/stdc++.h>
using namespace std;
//node representation
struct node {
int data;
struct node* next;
};
//pointer declaration
struct node* head;
struct node* tail = new node;
struct node* temp = new node;
struct node* curr;
struct node* pre;
void print_data(){
temp = head;
while(temp != NULL){
cout << temp -> data << " ";
temp = temp -> next;
}
}
struct node* find_and_append(int key, struct node* head){
//Declaration of pointers
curr = head; //represents the current pointer
struct node* last = tail;
struct node* prev = NULL;
struct node* prevToCurr = NULL; //represents the slow pointer
while (curr != tail)
{
//if the key value is found as the head pointer, the value
//of the head is updated and the node is inserted at the end.
if (curr -> data == key && prevToCurr == NULL)
{
prev = curr;
curr = curr -> next;
head = curr;
last -> next = prev;
last = last->next;
last -> next = NULL;
prev = NULL;
}
else
{
//if the value is found somewhere in between and
//not the head pointer.
if (curr -> data == key && prevToCurr != NULL)
{
prev = curr;
curr = curr -> next;
prevToCurr -> next = curr;
last -> next = prev;
last = last->next;
last -> next = NULL;
}
//if the curr -> data is not equal to the key, simply move the
//leading and trailing pointers
else if (curr != tail)
{
prevToCurr = curr;
curr = curr -> next;
}
}
}
return head;
}
int main(){
int n, num, key;
cout << "Enter the number of elements" <<endl;
cin >> n ;
//accepting list from user
cout << "Enter the elements: " <<endl;
do {
cin >> num;
if(head == NULL){
head = new node;
head -> data = num;
head -> next = NULL;
tail = head;
}
else{
struct node *new_node = new node;
new_node -> data = num;
new_node -> next = NULL;
tail -> next = new_node;
tail = new_node;
}
n = n - 1;
}while(n > 0);
print_data();
cout << "\nEnter the key: " <<endl;
cin >> key;
find_and_append(key, head);
print_data();
}
```

# A small example to understand the solution

Consider the linked list:

```
1 -> 3 -> 2 -> 3
key: 3
```

Initially the `head`

pointer would be pointing at the beginning of the linked list and the `tail`

pointer would be pointing to the end of linked list.

The `curr`

pointer would be traversing the linked list and the `prevToCurr`

would be the trailing pointer, one step behind the `curr`

pointer.

```
1 -> 3 -> 2 -> 3
curr tail
```

At the second step, the `curr -> data == 3`

which is the key value. A new node `prev`

would be containing the data value 3. This new node would be appended to the end of the list. The position of the tail pointer and the links would be updated where, `curr`

would point to node conntaining 2, and `prevToCurr`

would be at 1.

The list now becomes.

```
1 -> 2 -> 3 -> 3
curr tail
```

The `curr`

pointer would traverse forward and `prevToCurr`

would be one step behind it. When `curr -> data`

becomes equal to 3, A procedure similar to the second step is followed and it is appended to the end of the list.

When `curr == tail`

the program ends.

# Time Complexity

**Time complexity**: The time complexity of this approach is given by O(N), where, N is the number of nodes in the linked list. As we traverse all the N nodes in one pass.