Question

Question:

Rotate and sort the list:-  

In this problem, you have to first implement a singly linked list whose each node should have the following attributes,

● key - a positive integer

● next - address/pointer/reference to the next node in the linked list You will receive Q1 queries of following types,

● 1 x - Append a node to the linked list whose key should be x. After appending, print, in a new line, the key of each node in the linked list separated by a single space.

● 2 x - Delete the node in the linked list whose key is x.If such a node is not present in the linked list, no changes should be made. After this, print, in a new line, the key of each node in the linked list separated by a single space. The deleted node, if any, should be added in another linked list. Then you will receive Q2 queries of the following type,

● k - The linked list should be rotated towards right by |k| steps if k > 0, otherwise the linked list should be rotated towards left by |k| steps. k will always be an integer. Once all of the above Q2 queries are done, print, in a new line, the key of each node in the linked list separated by a single space. Then you have to merge the two linked lists together after sorting (by key), each of them using the merge sort algorithm. Once done, print in a new line, the key of each node in the linked list separated by a single space. Note that the linked list in the end should also be sorted by key.

Input Format - The first line will contain a positive integer, Q1 , following which there will be Q1 lines containing queries as described above. Then the very next line will contain a positive integer Q2 following which will be Q2 lines containing queries as described above.

Output Format - Q1 + 2 lines with space separated values of the key of each node in the linked list as explained above.

Constraints ● 0 < Q1 < 1000

● 0 < Q2 < 10000

● 0 < key, x < 1000

● -100 < k < 100

Answer 1

#include <iostream>
using namespace std;
//defining node of a linked list
class Node  
{  
    public: 
    int data;  
    Node *next;  
};
//appending node to the end of linked list
void append(Node** head_ref, int new_data)   
{   
    Node* new_node = new Node();  
    Node *last = *head_ref;  
    new_node->data = new_data;   
    new_node->next = NULL;   
    if (*head_ref == NULL)   
    {   
        *head_ref = new_node;   
        return;   
    }    
    while (last->next != NULL)   
        last = last->next;   
    last->next = new_node;   
    return;   
}   
//deleting node of the linked list
void deleteNode(struct Node **head_ref, int key) 
{ 
   if (*head_ref == NULL) 
      return; 
   Node* temp = *head_ref; 
   if (temp->data==key) 
    { 
        *head_ref = temp->next;   // Change head 
        free(temp);               // free old head 
        return; 
    } 
  
    // Find previous node of the node to be deleted 
    for (int i=0; temp!=NULL && temp->data!=key; i++) 
         temp = temp->next; 
  
    // If position is more than number of nodes 
    if (temp == NULL || temp->next == NULL) 
         return; 
    Node *next = temp->next->next; 
    free(temp->next);  // Free memory 
    temp->next = next;  // Unlink the deleted node from list 
}
//rotating a linked list if k is negative(i.e counter clockwise)
void rotate_left(Node** head_ref, int k)
{
    if (k == 0)
        return;
    Node* current = *head_ref;
    int count = 1;
    while (count < k && current != NULL) {
        current = current->next;
        count++;
    }
    if (current == NULL)
        return;
    Node* kthNode = current;
    while (current->next != NULL)
        current = current->next;
    current->next = *head_ref;
    *head_ref = kthNode->next;
    kthNode->next = NULL;
} 
//function to rotate linked list towards right clockwise by k
Node* rotate_right(Node* head, int k) 
{ 
    if (!head) 
        return head; 
    Node* tmp = head; 
    int len = 1; 
    while (tmp->next != NULL) { 
        tmp = tmp->next; 
        len++; 
    } 
    if (k > len) 
        k = k % len; 
    k = len - k; 
    if (k == 0 || k == len) 
        return head; 
    Node* current = head; 
    int cnt = 1; 
    while (cnt < k && current != NULL) { 
        current = current->next; 
        cnt++; 
    } 
    if (current == NULL) 
        return head; 
    Node* kthnode = current; 
    tmp->next = head; 
    head = kthnode->next; 
    kthnode->next = NULL; 
    // Return the updated head pointer 
    return head; 
} 
//function which return size of the node
int linked_list_size(Node *head)
{
    Node *temp = head;
    int count = 0;
    while(temp!=NULL)
    {
       temp = temp->next;
       count++;
    }
    return count;
}
//function to print the node
void printList(Node* head)
{
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
}
int main() {
    int q1,q2;
    cin>>q1;
    Node* head = NULL;
    for(int i=0;i<q1;i++)
    {
        int sub_query_no,key;
        cin>>sub_query_no>>key;
        if(sub_query_no==1)
        {
            append(&head,key);
        }
        else
        {
            deleteNode(&head,key);
        }
        printList(head);
        cout<<endl;
    }
    int size = linked_list_size(head);
    cin>>q2;
    for(int i=0;i<q2;i++)
    {
        int k;
        cin>>k;
        if(k>=0)
        { 
           k = k%size;
           head =  rotate_right(head,k);
           printList(head);
           cout<<endl;
        }
        else
        {
            k = -1*k;
            k = k%size;
            rotate_left(&head,k);
            printList(head);
            cout<<endl;
        }
    }
}

INPUT AND OUTPUT