1. Singly Linked List

---

#include <bits/stdc++.h>
using namespace std;
 
// ── NODE STRUCTURE ───────────────────────────────────────────────
class node {
public:
    int value;
    node* next;
    node(int val) {
        value = val;
        next = NULL;
    }
};
 
// ── INSERT AT TAIL ───────────────────────────────────────────────
// called 5 times: insertAtTail(1), (2), (3), (4), (5)
//
// after (1):  [1]->NULL
// after (2):  [1]->[2]->NULL
// after (3):  [1]->[2]->[3]->NULL
// after (4):  [1]->[2]->[3]->[4]->NULL
// after (5):  [1]->[2]->[3]->[4]->[5]->NULL
void insertAtTail(node* &head, int value) {
    node* newNode = new node(value);
    if (head == NULL) {
        head = newNode;
        return;
    }
    node* curr = head;
    while (curr->next != NULL)           // traverse to last node
        curr = curr->next;
    curr->next = newNode;
}
 
// ── INSERT AT HEAD ───────────────────────────────────────────────
// insertAtHead(0)
//
// before: [1]->[2]->[3]->[4]->[5]->NULL
// after:  [0]->[1]->[2]->[3]->[4]->[5]->NULL
void insertAtHead(node* &head, int value) {
    node* newNode = new node(value);
    newNode->next = head;                // new node points to old head
    head = newNode;                      // head moves to new node
}
 
// ── DELETE AT HEAD ───────────────────────────────────────────────
// deleteAtHead()
//
// before: [0]->[1]->[2]->[3]->[4]->[5]->NULL
// after:  [1]->[2]->[3]->[4]->[5]->NULL
void deleteAtHead(node* &head) {
    if (head == NULL) {
        cout << "empty\n";
        return;
    }
    node* toDelete = head;
    head = head->next;
    delete toDelete;
}
 
// ── DELETE BY VALUE ──────────────────────────────────────────────
// deleteByValue(3)
//
// before: [1]->[2]->[3]->[4]->[5]->NULL
// after:  [1]->[2]->[4]->[5]->NULL
void deleteByValue(node* &head, int val) {
    if (head == NULL) {
        cout << "empty\n";
        return;
    }
    if (head->next == NULL) {
        deleteAtHead(head);
        return;
    }
    node* curr = head;
    while (curr->next->value != val)     // stop at node BEFORE target
        curr = curr->next;
    node* toDelete = curr->next;
    curr->next = curr->next->next;       // bypass target node
    delete toDelete;
}
 
// ── DISPLAY ──────────────────────────────────────────────────────
// list state: [1]->[2]->[4]->[5]->NULL
// output:     1->2->4->5->NULL
void display(node* head) {
    while (head != NULL) {
        cout << head->value << "->";
        head = head->next;
    }
    cout << "NULL\n";
}
 
// list state: [1]->[2]->[4]->[5]->NULL
// output:     1->2->4->5->NULL  (same, just recursive)
void displayRecursive(node* head) {
    if (head == NULL) {
        cout << "NULL\n";
        return;
    }
    cout << head->value << "->";
    displayRecursive(head->next);   // direct call 
}
 
// list state: [1]->[2]->[4]->[5]->NULL
// output:     <-5<-4<-2<-1  (prints backward using call stack, list unchanged)
void reversePrint(node* head) {
    if (head == NULL) return;
    reversePrint(head->next);
    cout << "<-" << head->value;
}
 
// ── SEARCH ───────────────────────────────────────────────────────
// list state: [1]->[2]->[4]->[5]->NULL
// search(4) → 1 (found)
// search(9) → 0 (not found)
bool search(node* head, int key) {
    while (head != NULL) {
        if (head->value == key) return true;
        head = head->next;
    }
    return false;
}
 
// ── REVERSE (iterative) ──────────────────────────────────────────
// before: [1]->[2]->[4]->[5]->NULL
// after:  [5]->[4]->[2]->[1]->NULL
node* reverseIterative(node* &head) {
    if (head == NULL or head->next == NULL) return head;
 
    node* prev = NULL;
    node* cur = head;
    node* next;
    while (true) {
        next = cur->next;                // save next
        cur->next = prev;                // flip pointer
        prev = cur;                      // move prev forward
        cur = next;                      // move cur forward
        if (next == NULL) break;
    }
    return prev;                         // prev is new head
}
 
// ── REVERSE (recursive) ──────────────────────────────────────────
// before: [5]->[4]->[2]->[1]->NULL
// after:  [1]->[2]->[4]->[5]->NULL
node* reverseRecursive(node* &head) {
    if (head == NULL || head->next == NULL) return head;
    node* newhead = reverseRecursive(head->next);
    head->next->next = head;             // next node points back to current
    head->next = NULL;                   // current's next = NULL
    return newhead;
}
 
// ── MAIN ─────────────────────────────────────────────────────────
int main() {
    node* head = NULL;
    insertAtTail(head, 1);
    insertAtTail(head, 2);
    insertAtTail(head, 3);
    insertAtTail(head, 4);
    insertAtTail(head, 5);
    display(head);                       // 1->2->3->4->5->NULL
 
    insertAtHead(head, 0);
    display(head);                       // 0->1->2->3->4->5->NULL
 
    deleteAtHead(head);
    display(head);                       // 1->2->3->4->5->NULL
 
    deleteByValue(head, 3);
    display(head);                       // 1->2->4->5->NULL
 
    cout << search(head, 4) << "\n";     // 1
    cout << search(head, 9) << "\n";     // 0
 
    displayRecursive(head);              // 1->2->4->5->NULL
    reversePrint(head); cout << "\n";    // <-5<-4<-2<-1
 
    head = reverseIterative(head);
    display(head);                       // 5->4->2->1->NULL
 
    head = reverseRecursive(head);
    display(head);                       // 1->2->4->5->NULL
 
    return 0;
}

---