1. Linked-list fundamnetals

A linked list is a linear collection of nodes where each node stores:

• value – the payload
• next – a pointer to the following node (or nullptr)

Variants:

• Singly linked list – one pointer per node
• Doubly linked list – prev + next
• Circular linked list – tail points back to head

Memory is non-contiguous; traversal is pointer-chasing. This gives:

• O(1) insertion / deletion once the position is known
• O(n) random access

Minimal node definition:

struct Node {
    int val;
    Node* next;
    explicit Node(int v, Node* n = nullptr) : val(v), next(n) {}
};

A lightweight wrapper:

class SinglyList {
public:
    SinglyList() : head(new Node(0)) {}  // dummy
    ~SinglyList() { /* free memory */ }
private:
    Node* head;n};

2. LeetCode 203 – Remove Linked List Elements

Delete every node whose val == target and return the new head.

Iterative two-phase approach

class Solution {
public:
    Node* removeElements(Node* head, int target) {
        // 1. strip leading matches
        while (head && head->val == target) {
            Node* tmp = head;
            head = head->next;
            delete tmp;
        }
        if (!head) return nullptr;

        // 2. walk the rest
        Node* cur = head;
        while (cur->next) {
            if (cur->next->val == target) {
                Node* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        return head;
    }
};

Dummy-head trick

Introduce a sentinle node so every deletion is a middle-node deletion.

class Solution {
public:
    Node* removeElements(Node* head, int target) {
        Node dummy(0, head);
        Node* prev = &dummy;
        while (prev->next) {
            if (prev->next->val == target) {
                Node* del = prev->next;
                prev->next = del->next;
                delete del;
            } else {
                prev = prev->next;
            }
        }
        return dummy.next;
    }
};

3. LeetCode 707 – Design Linked List

Implement a singly linked list supporting:

• get(index)
• addAtHead(val)
• addAtTail(val)
• addAtIndex(index,val)
• deleteAtIndex(index)

Skeleton

class MyLinkedList {
    struct Node {
        int val;
        Node* next;
        Node(int v = 0, Node* n = nullptr) : val(v), next(n) {}
    };

    Node* dummy;
    int   len;

public:
    MyLinkedList() : dummy(new Node), len(0) {}

    int get(int index) {
        if (index < 0 || index >= len) return -1;
        Node* cur = dummy->next;
        while (index--) cur = cur->next;
        return cur->val;
    }

    void addAtHead(int val) { addAtIndex(0, val); }

    void addAtTail(int val)  { addAtIndex(len, val); }

    void addAtIndex(int index, int val) {
        if (index < 0 || index > len) return;
        Node* prev = dummy;
        while (index--) prev = prev->next;
        prev->next = new Node(val, prev->next);
        ++len;
    }

    void deleteAtIndex(int index) {
        if (index < 0 || index >= len) return;
        Node* prev = dummy;
        while (index--) prev = prev->next;
        Node* del = prev->next;
        prev->next = del->next;
        delete del;
        --len;
    }
};

4. LeetCode 206 – Reverse Linked List

Reverse the links in place and return the new head.

Iterative three-pointer technique

class Solution {
public:
    Node* reverseList(Node* head) {
        Node* prev = nullptr;
        Node* cur  = head;
        while (cur) {
            Node* nxt   = cur->next;
            cur->next   = prev;
            prev        = cur;
            cur         = nxt;
        }
        return prev;
    }
};

Recursive variant

Transform the loop into tail recursion:

class Solution {
    Node* helper(Node* prev, Node* cur) {
        if (!cur) return prev;
        Node* nxt = cur->next;
        cur->next = prev;
        return helper(cur, nxt);
    }
public:
    Node* reverseList(Node* head) {
        return helper(nullptr, head);
    }
};

Key takeaways

• A dummy (sentinel) node unifies edge cases.
• Pointer manipulation boils down to careful sequencing of assignments.
• Recursion mirrors iterative pointer updates; understnading the iterative version first makes the recursive rewrite straightforward.