Singly List Questions, DSA in C++

Problem 1: Search in Linked List

Problem Statement: Check karo ki linked list mein koi value present hai ya nahi.

Logic:

Sabse pehle ek temporary node banayenge temp aur use head se initialize kar denge.
Phir ek while loop lagayenge while(temp != NULL) ye condition tab hit karegi jab linked list ka end ho jayega.
while loop ke andar hame har node ka data aur given value ko compare karna hai if(temp->data == value) is condition ke true hone par ham true return kar denge.
Agar condition hit nhi hoti hai to ham har baar temp ko ek step aage badha denge temp = temp->next.
datawhile loop complete ho gyi lekin abhi tak function return nhi hua to iska matlab value present nhi hai to isliye false return kar denge.

Search Function:

bool search(Node* head, int key) {
  Node* temp = head;
  while (temp != NULL) {
    if (temp->data == key) {
      return true;
    }
    temp = temp->next;
  }
  return false;
}

Full Code:

#include <iostream>
using namespace std;

class Node
{
public:
    int data;
    Node *next;

    Node(int val)
    {
        data = val;
        next = NULL;
    }
};
bool search(Node *head, int key)
{
    Node *temp = head;
    while (temp != NULL)
    {
        if (temp->data == key)
        {
            return true;
        }
        temp = temp->next;
    }
    return false;
}
int main()
{
    Node *head = new Node(10);
    Node *second = new Node(20);
    Node *third = new Node(30);

    head->next = second;
    second->next = third;
    third->next = NULL;

    cout << search(head, 20);
}

Sample Input:

List = 10 -> 20 -> 30

Key = 20

Output:

true

Problem 2: Delete Node By Value

Problem Statement: Aapko ek value di gayi hai. Us value wale node ko list se delete karna hai (sirf pehla match)

Logic:

Firstly ham check karenge kiya linked list empty to nhi hai ? iske liye hame ye condition check karni hai, head == NULL
If yes to function ko yahi se ham return kar denge kioki agar linked list empty hi hai to node delete kese karenge.
Second ham is if(head->data) == val condtion se ye case handle karenge kiya current node head hai ya nhi ?
If yes to ham ek temporary node temp banayenge aur use head assign kar denge, phir head head ko head->next assign kar denge jisse head ab NULL ko point kar raha hai. Phir temp node ko delete kar denge aur function return kar denge.
Else ab ham ek previous node banayenge aur use head assign kar denge Node *prev = head aur hame jo node delete karna hai usse ek node pehle tak traverse karna hai using while loop with condition (prev->next != NULL && prev->next->data != val) aur har baar prev = prev->next iske baad ek if condition lagani hai if(prev->next == NULL) jo ye check karegi kiya list mein element present hai ya nhi if no to ye function yahi se return ho jayega.
If yes to ham ek new node banayenge Node* toDelete = prev->next ye wo node hoga jo actually mein delete karna hai.
Ab prev->next = prev->next->next is statement se ham us node ko list se unlink kar denge jo delete karna hai.
delete toDelete statement se ham us node ki memory ko free kar denge.

Delete By Value Function:

void deleteByValue(Node*& head, int val) {
    if (head == NULL) return;

    // Special case: delete head node
    if (head->data == val) {
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }

    // Traverse to find the node before the one to delete
    Node* prev = head;
    while (prev->next != NULL && prev->next->data != val) {
        prev = prev->next;
    }

    if (prev->next == NULL) return; // Value not found

    Node* toDelete = prev->next;
    prev->next = prev->next->next;
    delete toDelete;
}

Full Code:

#include <iostream>
using namespace std;
class Node
{
public:
    int data;
    Node *next;


    Node(int val)
    {
        data = val;
        next = NULL;
    }
};

void deleteByValue(Node *&head, int val)
{
    if (head == NULL)
        return;
    // Special case: delete head node
    if (head->data == val)
    {
        Node *temp = head;
        head = head->next;
        delete temp;
        return;
    }

    // Traverse to find the node before the one to delete
    Node *prev = head;
    while (prev->next != NULL && prev->next->data != val)
    {
        prev = prev->next;
    }


    if (prev->next == NULL)
        return; // Value not found


    Node *toDelete = prev->next;
    prev->next = prev->next->next;
    delete toDelete;
}

void printLL(Node *head)
{
    Node *temp = head;
    while (temp != NULL)
    {
        cout << temp->data << "->";
        temp = temp->next;
    }
    cout << "NULL" << endl;
}

int main(int argc, char const *argv[])
{
    Node *head = new Node(10);
    Node *second = new Node(20);
    Node *third = new Node(30);


    head->next = second;
    second->next = third;
    third->next = NULL;

    cout << "Linked List Before Delete : ";
    printLL(head);
    deleteByValue(head, 20);
    cout << "Linked List After Delete : ";
    printLL(head);


    return 0;
}

Sample Input:

List = 10 -> 20 -> 30

Key = 20

Output:

Linked List Before Delete : 10->20->30->NULL

Linked List After Delete : 10->30->NULL

Problem 3: Find Middle Node

Problem Statement: Ek singly linked list ka middle element find out karna hai.

Logic: Is problem ko solve karne ke liye ham ek classical approach ka use karenge which is slow-fast pointer approach. Is approach mein ham two nodes create karte hai called slow and fast aur slow ko one step se increase karte hai aur fast ko two steps se increase karte hai.

Firstly ham ye check karenge kiya hamari linked list empty to nhi hai using if(head == NULL) if yes then return -1 (Empty Linked List Case).
Second ham two nodes create karenge Node *slow = head and Node *fast = head. Yaha hamne dono pointers ko linked list ke start se initialize kar diya.
Ab yaha Logic ye hai ki agar ham slow ko one step aur fast ko two step se increase kare to jab fast linked list ke end par hoga tab slow linked list ke mid par hoga agar even linked list hai to mid+1 element return hoga.
Ab linked list ke end ko determine karne ke liye ham ek while loop chalayenge while(fast != NULL && fast->next != NULL). Hamne while loop mein two conditions ka use kara hai. Pehli condition tab hit hogi jab linked list even aur dusri jab hit hogi jab linked list odd hai.
while loop mein hame har baar slow ko one step aur fast ko two step increase karna hai. slow = slow->next and (fast = fast->next->next .
At the end hame slow->data return karna hai kioki ab slow exact middle of linked list par hai.

Find Middle Function:

int findMiddle(Node* head) {
    if (head == NULL) return -1;

    Node* slow = head;
    Node* fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow->data;
}