৭-৬ঃ Take Singly Linked List Input Recap

এবার আমরা লিঙ্কড লিস্টে ইনপুট নেওয়া রিকেপ করব।

লিঙ্কড লিস্টের ইনপুট নরমালি -1 দিয়ে টারমিনেট করা হয়। আমরা ইনপুট ভেলু নিয়ে তা দিয়ে নোড ক্রিয়েট করে লিঙ্কড লিস্টে ইনসার্ট করতে থাকব যতক্ষন না আমরা ইনপুটে -1 পাচ্ছি। আগের মডিউলে আমরা ইনসার্ট টেলে করতাম এবং সেটার কমপ্লেক্সিটি ছিল 0(N)। এই মডিউলে আমরা অপ্টিমাইজ ওয়ে শিখেছি। আমরা দেখেছি টেল ট্র্যাক রেখে টেলে ইনসার্ট করলে O(1) কমপ্লেক্সিটিতে করা যায়। তাই এবার আমরা তাই করব। এক্ষেত্রে 1 টি ভেলু ইনসার্ট করার কমপ্লেক্সিটি হবে O(1) এবং N টি ভেলু ইনসার্ট করার কমপ্লেক্সিটি হবে O(N)

#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_tail(Node *&head, Node *&tail, int val)
{
    Node *newNode = new Node(val);     // টেল ট্র্যাক রেখে ইনসার্ট করা হচ্ছে, যার কমপ্লেক্সিটি O(1)
    if (head == NULL)
    {
        head = newNode;
        tail = newNode;
        return;
    }
    tail->next = newNode;
    tail = newNode;
}
void print_linekd_list(Node *head)
{
    Node *tmp = head;
    while (tmp != NULL)
    {
        cout << tmp->val << " ";
        tmp = tmp->next;
    }
    cout << endl;
}
int main()
{
    Node *head = NULL;
    Node *tail = NULL;
    int val;
    while (true)
    {
        cin >> val;         // ভেলু ইনপুট নিচ্ছি। 
        if (val == -1)      // ভেলুটি -1 হলে ব্রেক করে দিচ্ছি। 
            break;
        insert_tail(head, tail, val);    // ইনসার্ট টেল ফাংশনকে কল করে টেলে ইনসার্ট করা হচ্ছে।
    }
    print_linekd_list(head);
    return 0;
}