Classic Linked List Problems

Reverse the list

Turn every arrow around. Keep three pointers: previous, current, and next (so you don't lose the rest):

#include <iostream>
using namespace std;

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

Node* reverseList(Node* head) {
    Node* prev = nullptr;
    Node* cur = head;
    while (cur) {
        Node* nxt = cur->next;   // remember the rest
        cur->next = prev;        // turn the arrow around
        prev = cur;
        cur = nxt;
    }
    return prev;
}

int main() {
    Node* head = reverseList(new Node(1, new Node(2, new Node(3, new Node(4)))));
    for (Node* c = head; c; c = c->next) cout << c->value << ' ';
    cout << endl;
    return 0;
}

Output

4 3 2 1 

Middle node and cycles: slow and fast pointers

Move slow one step and fast two steps. When fast reaches the end, slow is in the middle. If the list loops, fast eventually laps slow and they meet:

#include <iostream>
using namespace std;

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

int middle(Node* head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow->value;
}

bool hasCycle(Node* head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

int main() {
    Node* c = new Node(3);
    Node* head = new Node(1, new Node(2, c));
    cout << "middle: " << middle(new Node(1, new Node(2, new Node(3, new Node(4, new Node(5)))))) << endl;
    cout << "cycle? " << hasCycle(head) << endl;
    c->next = head;              // make a loop
    cout << "cycle? " << hasCycle(head) << endl;
    return 0;
}

Output

middle: 3
cycle? 0
cycle? 1

Think of it like this: Two runners on a track, one twice as fast: when the fast one finishes, the slow one is halfway. On a circular track, the fast one eventually catches up from behind.

Remember: Slow/fast pointers (Floyd's tortoise and hare) solve many linked list puzzles in O(n) time and O(1) memory.