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 HEAD ───────────────────────────────────────────────
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
}
 
// ── INSERT AT TAIL ───────────────────────────────────────────────
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;
}
 
// ── DELETE AT HEAD ───────────────────────────────────────────────
void deleteAtHead(node* &head) {
    if (head == NULL) {
        cout << "empty\n";
        return;
    }
    node* toDelete = head;
    head = head->next;
    delete toDelete;
}
 
// ── DELETE BY VALUE ──────────────────────────────────────────────
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 ──────────────────────────────────────────────────────
void display(node* head) {
    while (head != NULL) {
        cout << head->value << "->";
        head = head->next;
    }
    cout << "NULL\n";
}
 
void displayRecursive(node* head) {
    if (head == NULL) {
        cout << "NULL\n";
        return;
    }
    cout << head->value << "->";
    displayRecursive(head->next);   // direct call 
}
 
void reversePrint(node* head) {          // print in reverse without reversing list
    if (head == NULL) return;
    reversePrint(head->next);
    cout << "<-" << head->value;
}
 
// ── SEARCH ───────────────────────────────────────────────────────
bool search(node* head, int key) {
    while (head != NULL) {
        if (head->value == key) return true;
        head = head->next;
    }
    return false;
}
 
// ── REVERSE (iterative) ──────────────────────────────────────────
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) ──────────────────────────────────────────
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;
}
 
// ── REVERSE K NODES ──────────────────────────────────────────────
node* reverseKNodes(node* &head, int k) {
    node* cur = head;
    node* prev = NULL;
    node* next;
    int count = 0;
    while (cur != NULL && count < k) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
        count++;
    }
    if (next != NULL)
        head->next = reverseKNodes(next, k);  // recurse on remaining list
    return prev;
}
 
// ── 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
 
    head = reverseKNodes(head, 2);
    display(head);                       // 2->1->5->4->NULL
 
    return 0;
}

---