Data Structure in C++: Single Linked List (Part 4)

Order

Take a singly linked list as input and sort it in descending order. Then print the list.

Sample Input

1 4 5 2 7 -1

Sample Output

7 5 4 2 1

Sample Input

20 40 30 10 50 60 -1

Sample Output

60 50 40 30 20 10

Try on your own first.

Data Structure in C++: Single Linked List (Part-1)

Answer:

#include <bits/stdc++.h>
using namespace std;
class Node {
public:
    int val;
    Node* next;
    Node(int val) {
        this->val = val;
        this->next = NULL;
    }
};
// Function to sort the linked list in descending order
Node* sortDescending(Node* head) {
    vector<int> values;
    Node* temp = head;
    // Store all values in a vector
    while (temp != NULL) {
        values.push_back(temp->val);
        temp = temp->next;
    }
    // Sort the values in descending order
    sort(values.rbegin(), values.rend());
    // Reconstruct the linked list with sorted values
    temp = head;
    for (int val : values) {
        temp->val = val;
        temp = temp->next;
    }
    return head;
}
// Function to print the linked list
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->val << " ";
        temp = temp->next;
    }
    cout << endl;
}
int main() {
    Node* head = NULL;
    Node* tail = NULL;
    int val;
    // Input the linked list
    while (cin >> val && val != -1) {
        Node* new_node = new Node(val);
        if (head == NULL) {
            head = tail = new_node;
        } else {
            tail->next = new_node;
            tail = new_node;
        }
    }
    // Sort and print the list in descending order
    head = sortDescending(head);
    printList(head);
    return 0;
}

Queries

Problem Statement

You have a singly linked list which is empty initially. Then you will be given Q queries. In each query you will be given two values X and V.

• If X is 0 that means you will insert the value V to the head of the linked list.
• If X is 1 then you will insert the value V to the tail of the linked list.
• If X is 2 then you will delete the value Vth index of the linked list. Assume that index starts from 0. If the index is invalid, then you shouldn’t perform the deletion.
• After each query you need to print the linked list.

Note: You must use singly linked list, otherwise you will not get marks.

Input Format

• First line will contain Q.
• Next Q lines will contain X and V.

Constraints

1. 1 <= Q <= 1000;
2. 0 <= X <= 2;
3. 0 <= V <= 1⁰⁹

Output Format

• For each query ouput the updated linked list.

Sample Input 0

4
0 10
1 20
1 30
0 40

Sample Output 0

10 
10 20 
10 20 30 
40 10 20 30

Sample Input 1

11
0 10
2 5
1 20
1 30
0 40
2 0
0 50
2 2
1 60
2 3
2 3

Sample Output 1

10 
10 
10 20 
10 20 30 
40 10 20 30 
10 20 30 
50 10 20 30 
50 10 30 
50 10 30 60 
50 10 30 
50 10 30

Sample Input 2

10
1 4
2 1
0 9
0 10
2 2
1 5
2 0
2 1
2 5
2 2

Sample Output 2

4 
4 
9 4 
10 9 4 
10 9 
10 9 5 
9 5 
9 
9 
9

Try on your own.

Photo by JJ Ying on Unsplash

Answer:

#include<bits/stdc++.h>
using namespace std;
    class Node
    {
        public:
        int val;
        Node* next;
        Node (int val){
            this->val=val;
            this->next=NULL;
        }
    };
    void insert_at_head(Node*&head, int v){
        Node*newNode= new Node(v);
        newNode->next=head;
        head=newNode;
    }
    void insert_at_tail(Node*&head, int v){
        Node*newNode=new Node(v);
        if(head==NULL){
            head=newNode;
            return;
        }
        Node*tmp=head;
        while(tmp->next!=NULL){
            tmp=tmp->next;
        }
        tmp->next=newNode;
    }
    void delete_index(Node*&head, int index){
        if(head==NULL || index<0){
            return;
        }
        if(index==0){
            Node*tmp=head;
            head=head->next;
            delete tmp;
            return;
        }
        Node*tmp=head;
        for(int i=0;i<index-1;i++){
            if(tmp==NULL || tmp->next==NULL){
                return;
            }
            tmp=tmp->next;
        }
        Node*deleteNode=tmp->next;
        if(deleteNode!=NULL){
        tmp->next=deleteNode->next;
        delete deleteNode;
        }
    }
    void print_linked_list(Node*head){
        Node*tmp=head;
        while(tmp!=NULL){
            cout<<tmp->val<<" ";
            tmp=tmp->next;
        }
        cout<<endl;
    }
    int main(){
        int Q;
        cin>>Q;
        Node* head = NULL;
        while(Q--){
            int x,v;
            cin>>x>>v;
            if(x==0){
                insert_at_head(head, v);
            }
            else if(x==1){
                insert_at_tail(head, v);
            }
            else if(x==2){
                delete_index(head, v);
            }
            print_linked_list(head);
        }
        return 0;
    }

Remove Duplicate

Problem Statement

You will be given a singly linked list of integer values as input. You need to remove duplicate values from the linked list and finally print the linked list.

The process is, for each node N, traverse from that node and delete all nodes where the values are same with N.

Note: You must use singly linked list, otherwise you will not get marks.

Input Format

• First line will contain the values of the singly linked list, and will terminate with -1.

Constraints

1. 1 <= N <= 1000; Here N is the maximum number of nodes of the linked list.
2. 0 <= V <= 1000; Here V is the value of each node.

Output Format

• Output the final linked list where there will be no duplicate values.

Sample Input 0

1 2 3 4 5 -1

Sample Output 0

1 2 3 4 5

Sample Input 1

1 2 4 2 3 5 1 4 5 2 6 1 -1

Sample Output 1

1 2 4 3 5 6

Sample Input 2

5 5 1 1 2 4 2 4 1 3 5 0 -1

Sample Output 2

5 1 2 4 3 0

Sample Input 3

10 10 10 20 20 20 10 20 -1

Sample Output 3

10 20

Try on your own.

Data Structure in C++: Single Linked List (Part 3)

Answer:

#include<bits/stdc++.h>
using namespace std;
    class Node
    {
        public:
        int val;
        Node* next;
        Node (int val){
            this->val=val;
            this->next=NULL;
        }
    };
    void duplicate_elements(Node*head){
        Node* present=head;
        while(present!=NULL){
            Node* future=present;
            while(future->next!=NULL){
                if(present->val==future->next->val){
                    Node*tmp= future->next;
                    future->next=future->next->next;
                    delete tmp;
                }
                else{
                    future=future->next;
                }
            }
            present=present->next;
        }
    }
    void print_linked_list(Node*head){
        Node*present=head;
        while(present!=NULL){
            cout<<present->val<<" ";
            present=present->next;
        }
    }
    int main (){
    Node*head=NULL;
    Node*tail=NULL;
    int val;
    while(true){
        cin>>val;
        if(val==-1){
            break;
        }
        Node* new_node = new Node(val);
        if (head == NULL) {
            head = tail = new_node;
        }
        else {
            tail->next = new_node;
            tail = new_node;
        }
    }
    duplicate_elements(head);
    print_linked_list(head);
    Node*head2=NULL;
    Node*tail2=NULL;
    while(true){
        cin>>val;
        if(val==-1){
            break;
        }
        Node* new_node = new Node(val);
        if (head2 == NULL) {
            head2 = tail2 = new_node;
        }
        else {
            tail2->next = new_node;
            tail2 = new_node;
        }
    }
    duplicate_elements(head2);
    print_linked_list(head2);
    return 0;
    }

Thank you for being so patient. Please share, comment, and clap in my article.