Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Brute Force Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Time Complexity Analysis
2.2.2.
Space Complexity Analysis
3.
Optimized Approach
3.1.
Pseudocode
3.2.
Implementation in C++
3.2.1.
Time Complexity Analysis
3.2.2.
Space Complexity Analysis
4.
Frequently Asked Questions
4.1.
What are linked lists best used for?
4.2.
What type of memory is referred to for the linked list?
4.3.
What are the limitations of linked lists?
5.
Conclusion
Last Updated: Mar 27, 2024

Move all occurrences of an Element to end in a Linked List

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

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

  1. Iterate through the given Linked List and count the number of nodes with value = key and store it in countKey.
  2. Create an empty Linked List, say outputLinkedList.
  3. 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.
  4. 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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach

In this approach, we will optimize the previous one. If you can notice, we can modify our implementation to avoid creating a new Linked List. Instead, we can add a new node at the end of the input Linked List itself and make necessary changes to avoid an infinite loop.

Pseudocode

  1. Iterate through the input Linked List and store its size in a variable say sizeLinkedList.
  2. Create a variable Count and initialize it with 0.
  3. While Count < sizeLinkedList:
    1. If the value of the current node is not equal to the given key, increment the Count and Continue.
    2. Remove the current node and insert it at the end.
    3. Count += 1.

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;
   }
}

void removeNode(Node *prev, Node *node)
{
   if (prev == NULL)
   {
       node->next = NULL;
       return;
   }
   prev->next = node->next;
   node->next = NULL;
}

// 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, Node *endPointer, int key, int size)
{
   // Root of the output Linked list.
   Node *newRoot = root;

   // Utility pointer.
   Node *prev = NULL;

   // Traverse till the end of the input linked list.
   while (size > 0)
   {
       if (root->val == key)
       {
           // If the value of the node is equal to key, remove the node,
           // add a node at the end.

           // Prev pointer is used to store the pointer to the node which is just before the current node.
           if (prev == NULL)
           {
               newRoot = newRoot->next;
           }

           // Remove the node.
           removeNode(prev, root);

           // Add the node at the end.
           endPointer = addNodeAtEnd(endPointer, key);

           // Update the newRoot if it is NULL.
           if (newRoot == NULL)
           {
               newRoot = endPointer;
           }
       }

       // If not, update the prev pointer.
       if (root->val != key)
           prev = root;

       // If the val is equal to key, update the prev pointer accordingly.
       if (root->val == key)
       {
           if (prev != NULL)
               root = prev->next;
           else
               root = newRoot;
       }
       else
           root = root->next;
      
       // Decrement the size counter.
       size--;
   }

   // Print the linked list.
   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, endP, key, size);
}

 

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(1).

It is because we are not using any extra memory.

Frequently Asked Questions

What are linked lists best used for?

Linked lists are often used because of their efficient insertion and deletion. They can be used to implement stacks, queues, and other abstract data types.

What type of memory is referred to for the linked list?

Dynamic memory allocation is used to allocate memory to linked lists.

What are the limitations of linked lists?

The linked list requires more memory to store the elements than an array, because each node of the linked list points a pointer, due to which it requires more memory. It is very difficult to traverse the nodes in a linked list. In this, we cannot access randomly to any one node.

Conclusion

In this blog, we discussed an important question related to Linked Lists where we applied concepts of removing a node from a Linked List, adding a node at the end of a Linked List and a tricky implementation to solve the problem with better time and space complexity.

We have prepared a guide for you containing several standard problems asked in interviews related to Linked List. Please refer to this link to find the comprehensive list. It will help you in cracking coding rounds and interviews.

Recommended Problems -

You can also refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc., you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Previous article
Python Program to Reverse a Linked List
Next article
Rearrange a Linked List in place
Live masterclass