Single Linked List: Intermediate (Part-2)

Data Structure in C++

Question 1: Take two singly linked lists as input and check if their sizes are identical.

Sample Input

2 1 5 3 4 9 -1

1 2 3 4 5 6 -1

Sample Output

YES

Sample Input

5 1 4 5 -1
5 1 4 -1

Sample Output

NO

Try on your own first.

https://images.app.goo.gl/k1z9T2WZhE5GH2Zf8

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 compute the size of the linked list
int getSize(Node* head) {
    int size = 0;
    while (head != NULL) {
        size++;
        head = head->next;
    }
    return size;
}

int main() {
    Node *head1 = NULL, *tail1 = NULL;
    Node *head2 = NULL, *tail2 = NULL;
    int val;

    // Input the first linked list
    while (cin >> val && val != -1) {
        Node* new_node = new Node(val);
        if (head1 == NULL) {
            head1 = tail1 = new_node;
        } else {
            tail1->next = new_node;
            tail1 = new_node;
        }
    }

    // Input the second linked list
    while (cin >> val && val != -1) {
        Node* new_node = new Node(val);
        if (head2 == NULL) {
            head2 = tail2 = new_node;
        } else {
            tail2->next = new_node;
            tail2 = new_node;
        }
    }

    // Compare sizes
    if (getSize(head1) == getSize(head2)) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}

Question 2: Take a singly linked list as input and print the reverse of the linked list.

Sample Input

5 4 8 6 2 1 -1

Sample Output

1 2 6 8 4 5

Sample Input

1 2 3 4 -1

Sample Output

4 3 2 1

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 reverse the linked list using recursion
void recursiveReverse(Node* head) {
    if (head == NULL) return;
    recursiveReverse(head->next);
    cout << head->val << " ";
}

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

    // Print the reversed linked list
    recursiveReverse(head);
    cout << endl;

    return 0;
}

Question 3: Take a singly linked list as input and print the middle element. If there are multiple values in the middle print both.

Sample Input

2 4 6 8 10 -1

Sample Output

6

Sample Input

1 2 3 4 5 6 -1

Sample Output

3 4

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;
    }
};
// Function to print the middle element(s) of the linked list
void printMiddle(Node* head) {
    if (head == NULL) return;
    Node* slow = head;
    Node* fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    if (fast == NULL) {
        Node* midPrev = head;
        while (midPrev->next != slow) {
            midPrev = midPrev->next;
        }
        cout << midPrev->val << " " << slow->val << endl;
    } else {
        cout << slow->val << 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;
        }
    }
    // Print the middle element(s)
    printMiddle(head);

    return 0;
}

Question 4: Take a singly linked list as input, then print the maximum value of them.

Sample Input

2 4 1 3 5 4 2 5 -1

Sample Output

5

Sample Input

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

Sample Output

8

Try on your own first.

Photo by Kevin Woblick 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;
    }
};

// Function to find the maximum value in the linked list
int findMax(Node* head) {
    int maxValue = INT_MIN;
    while (head != NULL) {
        maxValue = max(maxValue, head->val);
        head = head->next;
    }
    return maxValue;
}

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;
        }
    }
    // Print the maximum value
    cout << findMax(head) << endl;
    return 0;
}

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