Single Linked List: Advanced (Part 3)

Data Structure in C++

Get Difference

Problem Statement

You need to take a singly linked list of integer value as input and print the difference between the maximum and minimum value of the singly linked list.

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

Input Format

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

Constraints

1. 1 <= N <= 10⁵; Here N is the maximum number of nodes of the linked list.
2. -10⁹ <= V <= 10⁹; Here V is the value of each node.

Output Format

• Output the difference between the maximum and minimum value.

Sample Input 0

2 4 1 5 3 6 -1

Sample Output 0

5

Sample Input 1

2 -1

Sample Output 1

0

Try on your own.

Photo by Claudio Schwarz 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;
        }
    };
    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;
        }
    }
    if(head==NULL){
        cout<< "Empty List"<< endl;
    }
    else{
        int max_value=head->val;
        int min_value=head->val;
        Node* current=head->next;
        while(current!=NULL){
        if(current->val>max_value){
            max_value=current->val;
        }
        if(current->val<min_value){
            min_value=current->val;
        }
        current=current->next;
    }
    int difference=max_value-min_value;
    cout<<difference<<endl;
    }
    return 0;
    }

Search

Problem Statement

You need to take a singly linked list of integer values as input. Afterward, you will be given an integer value X. Your task is to determine whether X is present in the linked list or not. If it is present, print its first index from the left side; otherwise, print -1. Assume that the linked list’s index starts with 0.

Note: You must use a singly linked list; otherwise, you will not receive marks.

Input Format

• First line will contain T, the number of test cases.
• First line of each test case will contain the values of the singly linked list, and will terminate with -1.
• Second line of each test case will contain X.

Constraints

1. 1 <= T <= 100
2. 1 <= N <= 10⁵; Here N is the maximum number of nodes of the linked list.
3. -10⁹ <= V <= 10⁹; Here V is the value of each node.
4. -10⁹ <= X <= 10⁹

Output Format

• Output the index of X in the linked list.

Sample Input 0

4
1 2 3 4 5 -1
3
1 2 3 -1
5
1 -1
1
10 20 -1
20

Sample Output 0

2
-1
0
1

Try on your own first.

Mohammed Muzahidul Islam - Medium

Answer:

#include<bits/stdc++.h>
using namespace std;
    class Node
    {
        public:
        int val;
        Node* next;
        Node (int val){
            this->val=val;
            this->next=NULL;
        }
    };
    int index_search(Node*head, int X){
        int index=0;
        Node*tmp=head;
        while(tmp!=NULL){
            if(tmp->val==X){
                return index;
            }
            tmp=tmp->next;
                index++;
        }
        return -1;
    }
    void print_linked_list(Node*head){
        Node*tmp=head;
        while(tmp!=NULL){
            cout<<tmp->val<<" ";
            tmp=tmp->next;
        }
    }
int main (){
    int t;
    cin>>t;
    while(t--){
    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;
        }
    }
    int X;
    cin>>X;

    int search_index= index_search(head, X);
    cout<<search_index<<endl;
    }
    return 0;
}

Same to Same

Problem Statement

You will be given two singly linked list of integer values as input. You need to check if all the elements of both list are same which means both list are same. If they are same print “YES” otherwise print “NO”.

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

Input Format

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

Constraints

1. 1 <= N1, N2 <= 1000; Here N1 and N2 is the maximum number of nodes of the first and second linked list.
2. 0 <= V <= 1000; Here V is the value of each node.

Output Format

• Output “YES” or “NO”.

Sample Input 0

10 20 30 40 -1
10 20 30 40 -1

Sample Output 0

YES

Sample Input 1

10 20 30 40 -1
10 20 30 -1

Sample Output 1

NO

Sample Input 2

10 20 30 40 -1
40 30 20 10 -1

Sample Output 2

NO

Try on your own first.

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

Answer:

#include<bits/stdc++.h>
using namespace std;
    class Node
    {
        public:
        int val;
        Node* next;
        Node (int val){
            this->val=val;
            this->next=NULL;
        }
    };
    bool same_to_same(Node* head,Node* head2){
        while(head!=NULL && head2!=NULL){
            if(head->val != head2->val){
                return false;
            }
            head=head->next;
            head2=head2->next;
        }
        return (head==NULL && head2==NULL);
    }
    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;
        }
    }
    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;
        }
    }
    if(same_to_same(head, head2)){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
    return 0;
    }

I appreciate your patience. Do share and follow.