C++ Program For Moving All Occurrences Of An Element To End In A Linked List

// C++ program to move all occurrences of a
// given key to end.
#include <bits/stdc++.h>

// A Linked list Node
struct Node {
    int data;
    struct Node* next;
};

// A utility function to create a new node.
struct Node* newNode(int x)
{
    Node* temp = new Node;
    temp->data = x;
    temp->next = NULL;
}

// Utility function to print the elements
// in Linked list
void printList(Node* head)
{
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("
");
}

// Moves all occurrences of given key to
// end of linked list.
void moveToEnd(Node* head, int key)
{
    // Keeps track of locations where key
    // is present.
    struct Node* pKey = head;

    // Traverse list
    struct Node* pCrawl = head;
    while (pCrawl != NULL) {
        // If current pointer is not same as pointer
        // to a key location, then we must have found
        // a key in linked list. We swap data of pCrawl
        // and pKey and move pKey to next position.
        if (pCrawl != pKey && pCrawl->data != key) {
            pKey->data = pCrawl->data;
            pCrawl->data = key;
            pKey = pKey->next;
        }

        // Find next position where key is present
        if (pKey->data != key)
            pKey = pKey->next;

        // Moving to next Node
        pCrawl = pCrawl->next;
    }
}

// Driver code
int main()
{
    Node* head = newNode(10);
    head->next = newNode(20);
    head->next->next = newNode(10);
    head->next->next->next = newNode(30);
    head->next->next->next->next = newNode(40);
    head->next->next->next->next->next = newNode(10);
    head->next->next->next->next->next->next = newNode(60);

    printf("Before moveToEnd(), the Linked list is
");
    printList(head);

    int key = 10;
    moveToEnd(head, key);

    printf("
After moveToEnd(), the Linked list is
");
    printList(head);

    return 0;
}

// C++ code to remove key element to end of linked list
#include<bits/stdc++.h>
using namespace std;

// A Linked list Node
struct Node 
{
    int data;
    struct Node* next;
};

// A utility function to create a new node.
struct Node* newNode(int x)
{
    Node* temp = new Node;
    temp->data = x;
    temp->next = NULL;
}

// Function to remove key to end
Node *keyToEnd(Node* head, int key)
{

    // Node to keep pointing to tail
    Node* tail = head;
    if (head == NULL) 
    {
        return NULL;
    }
    while (tail->next != NULL) 
    {
        tail = tail->next;
    }
    
    // Node to point to last of linked list
    Node* last = tail;
    Node* current = head;
    Node* prev = NULL;
    
    // Node prev2 to point to previous when head.data!=key
    Node* prev2 = NULL;
    
    // loop to perform operations to remove key to end
    while (current != tail) 
    {
        if (current->data == key && prev2 == NULL) 
        {
            prev = current;
            current = current->next;
            head = current;
            last->next = prev;
            last = last->next;
            last->next = NULL;
            prev = NULL;
        }
        else
        {
            if (current->data == key && prev2 != NULL)
            {
                prev = current;
                current = current->next;
                prev2->next = current;
                last->next = prev;
                last = last->next;
                last->next = NULL;
            }
            else if (current != tail) 
            {
                prev2 = current;
                current = current->next;
            }
        }
    }
    return head;
}

// Function to display linked list
void printList(Node* head) 
{
    struct Node* temp = head;
    while (temp != NULL) 
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}


// Driver Code
int main()
{
    Node* root = newNode(5);
    root->next = newNode(2);
    root->next->next = newNode(2);
    root->next->next->next = newNode(7);
    root->next->next->next->next = newNode(2);
    root->next->next->next->next->next = newNode(2);
    root->next->next->next->next->next->next = newNode(2);

    int key = 2;
    cout << "Linked List before operations :";
    printList(root);
    cout << "\nLinked List after operations :";
    root = keyToEnd(root, key);
    printList(root);
    return 0;
}

// This code is contributed by Rajout-Ji