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

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

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

Run Code

Input

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

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

Run Code

Output

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

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

Run Code

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 -

• Flattening A Linked List
• Sorted Doubly Linked List
• Linked List Cycle ii
   

You can also refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System 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 problems, interview 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!