📖 Chapter 2.7: Pointers and Memory

⏱ Estimated reading time: 90 minutes | Difficulty: 🟡 Beginner to Intermediate (the key to understanding C++)

📝 Prerequisites: Chapter 2.3 (functions, arrays, pass-by-reference), Chapter 2.4 (structs and classes)

Many beginners feel that pointers are "mysterious," "crash-prone," and "best avoided." But the truth is: pointers are the key to understanding how C++ uses memory. Once you build the mental picture that "variables live in memory, and every home has a house number," concepts that recur throughout the rest of the book—pointers, references, arrays, dynamic memory, linked lists, trees—suddenly click into place.

This chapter does not ask you to become a memory-management expert. Instead, it helps you build the correct mental model and master the pointer skills you will actually use in competitive programming.

Prerequisites

• Chapter 2.3: functions, arrays, pass-by-reference (& parameters)
• Chapter 2.4: structs and classes (pointers are heavily used with structs in linked lists/trees)
• Know that a variable is a "container that stores data"

🎯 Learning Objectives

After studying this chapter, you will be able to:

1. Understand the relationship between "memory," "address," and "pointer," and build a correct mental picture
2. Use the address-of operator & and the dereference operator *
3. Distinguish between pointers and references, and know when to use each
4. Understand the relationship between array names and pointers, and read pointer arithmetic
5. Use new / delete for dynamic memory allocation, and understand what a memory leak is
6. Use pointers to build the most basic linked list and binary tree nodes
7. Know when to use pointers and when not to in competitive programming
8. Understand multi-level pointers (int**), read dynamic 2D arrays and "pointers to pointers"
9. Use pointers to manipulate C-style strings (char*), hand-write strlen / strcpy
10. Know the basic syntax of function pointers, read callbacks and the mechanism behind custom sorting

2.7.1 Memory, Addresses, and Pointers: Build the Picture First

🏨 The Hotel Analogy

Imagine computer memory as a hotel with many rooms:

• Each room is one byte (or a group of bytes) of storage
• Each room has a room number—this is the memory address
• When you write int x = 42;, the compiler assigns variable x a room (say, room 1000) holding 42
• A pointer is a note with a "room number" written on it. It is not the data in the room itself, but information about "where a certain room is"

💡 Core sentence: A normal variable stores data; a pointer variable stores the address of another variable.

Address-of & and Dereference *

C++ provides two operators that are inverses of each other:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int x = 42;

    int* p = &x;   // p stores the address of x (p "points to" x)

    cout << x  << "\n";   // 42      —— the data in x
    cout << &x << "\n";   // 0x...   —— the address of x (may differ each run)
    cout << p  << "\n";   // 0x...   —— same as &x; this is what p stores
    cout << *p << "\n";   // 42      —— dereference: follow the address to x, read 42

    *p = 100;             // modify x through the pointer (follow the room number, change content)
    cout << x << "\n";    // 100     —— x really changed!

    return 0;
}

🤔 Are the * in int* p and the * in *p the same thing? No! This is the biggest source of confusion for beginners:

• In a declaration, the * in int* p means "p is a pointer to an int" (part of the type)
• In usage, the * in *p is the dereference operator, meaning "fetch the value p points to" Same symbol, two meanings, disambiguated by context.

Diagram: A pointer pointing to a variable

🎬 Interactive: See & and * Step by Step

This visualization breaks "take address → dereference-read → dereference-write" into 5 steps. Click "Next" and watch the memory rooms and the pointer arrow to see, with your own eyes, how *p = 100 reaches through the pointer to actually change x:

2.7.2 Null Pointers and nullptr

If a pointer does not yet point to any valid object, you should make it point to "nothing." Modern C++ uses nullptr to represent a null pointer:

int* p = nullptr;   // p points to nothing

if (p == nullptr) {
    cout << "p is null, cannot dereference\n";
}

// *p;   // ❌ Dangerous! Dereferencing a null pointer → crash (segfault)

⚠️ Do not use the old NULL or 0. Old code often writes int* p = NULL;, but NULL is essentially 0 and causes ambiguity in overload/template scenarios. Modern C++ always uses nullptr—type-safe and semantically clear.

🐛 The number-one crash cause: Dereferencing a null pointer or a "wild pointer" (one pointing to an invalid address). This is the most common source of Segmentation fault. Always verify a pointer is valid before dereferencing.

🧩 Distinguishing: & and * Each Have Two Faces

Both & and * are "one symbol, several meanings," disambiguated by context. Once a beginner separates these clearly, half of pointers is understood:

💡 One-line memory aid: standing alone next to a variable/pointer → address-of / dereference; squeezed between two numbers → AND / multiply; following a type → reference / pointer declaration.

2.7.3 Pointer vs Reference: Which One Should You Use?

In Chapter 2.3 you already learned about references (int& r = x;). Both references and pointers can "indirectly access" another variable, but they have important differences.

int x = 10, y = 20;

// ---- Reference ----
int& r = x;    // r is an alias for x, must be bound at declaration
r = 100;       // directly changes x, x == 100
// r = y;      // this does NOT "rebind r to y"; it assigns y's value to x!
// once bound, a reference can never be rebound

// ---- Pointer ----
int* p = &x;   // p points to x
*p = 100;      // changes x, x == 100
p = &y;        // OK! a pointer can be reassigned to y
*p = 200;      // now changes y, y == 200
p = nullptr;   // a pointer can be null

Comparison Table

⚡ Rule of thumb for competitive programming:

• Prefer references. For passing parameters and avoiding copies of large objects, references are safer and cleaner (see const vector<int>& in Chapter 2.3).
• The few cases that need pointers: ① the target needs to change (e.g., traversing a linked list); ② you need to represent "no target" (nullptr, e.g., a tree's empty child); ③ dynamic memory allocation (new).

2.7.4 Pointers and Arrays: They Are Relatives

In C++, arrays and pointers are closely related. In most contexts, an array name "decays" into a pointer to its first element.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[5] = {10, 20, 30, 40, 50};

    int* p = arr;        // same as int* p = &arr[0]; the name decays to a first-element pointer

    cout << *p     << "\n";   // 10     —— arr[0]
    cout << *(p+1) << "\n";   // 20     —— arr[1]
    cout << *(p+2) << "\n";   // 30     —— arr[2]

    // The following four are completely equivalent:
    cout << arr[2]   << "\n"; // 30
    cout << *(arr+2) << "\n"; // 30
    cout << p[2]     << "\n"; // 30
    cout << *(p+2)   << "\n"; // 30

    return 0;
}

🤔 Why is arr[i] equivalent to *(arr + i)? Because the subscript operation arr[i] is essentially "offset i elements from the base address arr, then dereference." This also explains why array indices start at 0—the index is the "offset," and the first element has offset 0.

Pointer Arithmetic

Pointer +1 does not mean address +1 byte; it means advance by one element's size:

int arr[5] = {10, 20, 30, 40, 50};
int* p = arr;

// Assume int is 4 bytes and arr starts at address 1000:
// p   points to 1000 (arr[0])
// p+1 points to 1004 (arr[1]) —— automatically skips one int's 4 bytes
// p+2 points to 1008 (arr[2])

int arr[5] = {10, 20, 30, 40, 50};

// Method 1: traditional index
for (int i = 0; i < 5; i++) cout << arr[i] << " ";
cout << "\n";

// Method 2: pointer traversal (good to understand; rarely written this way in contests)
for (int* p = arr; p < arr + 5; p++) {
    cout << *p << " ";
}
cout << "\n";

⚡ Contest tip: In STL calls like sort(arr, arr + n) and lower_bound(arr, arr + n, x), arr and arr + n are exactly the "first-element pointer" and "past-the-end pointer." Once you understand array decay, you understand why these functions take such arguments.

2.7.5 Pointers as Function Parameters

In Chapter 2.3 we used references to let a function modify the original variable. You can also do this with pointers—the classic C style, still common in low-level code and linked-list/tree operations.

#include <bits/stdc++.h>
using namespace std;

// Using pointers: pass addresses, modify originals via dereference
void swapByPointer(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// Using references: cleaner (recommended)
void swapByRef(int& a, int& b) {
    int tmp = a;
    a = b;
    b = tmp;
}

int main() {
    int x = 1, y = 2;

    swapByPointer(&x, &y);   // must explicitly pass addresses &x, &y
    cout << x << " " << y << "\n";  // 2 1

    swapByRef(x, y);         // pass variables directly
    cout << x << " " << y << "\n";  // 1 2

    return 0;
}

💡 How to choose? In C++, use references when you can (clean syntax, can't be null). Typical cases that need pointers: the parameter might be nullptr ("optional" semantics), or you are writing a linked list/tree—structures naturally expressed with pointers.

2.7.6 Dynamic Memory: new and delete

So far, our array sizes were either known at compile time or handled by vector. There is a third way: manually request memory from the system at runtime, called dynamic memory allocation.

Stack Memory vs Heap Memory

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Dynamically allocate a single int
    int* p = new int;     // request one int on the heap
    *p = 42;
    cout << *p << "\n";   // 42
    delete p;             // must free after use! otherwise memory leak

    // Dynamically allocate an array (size known only at runtime)
    int n;
    cin >> n;
    int* arr = new int[n];   // request n ints on the heap
    for (int i = 0; i < n; i++) arr[i] = i * i;
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << "\n";
    delete[] arr;            // free an array with delete[] (with brackets)!

    return 0;
}

⚠️ Three Iron Rules

1. new pairs with delete, new[] pairs with delete[]. If you allocate an array with new[], you must free it with delete[], otherwise behavior is undefined.
2. Every new must have a matching delete. Otherwise you get a memory leak—allocated memory is never returned.
3. Do not use a pointer after delete (it becomes a "dangling pointer"); set p = nullptr; right after delete.

🤔 Do you actually use new/delete in contests? In the vast majority of cases: no! In contests the program exits right after running, and the OS reclaims all memory, so "memory leaks" are usually harmless; plus new/delete are verbose and error-prone.

• Need a dynamic array? → use vector (auto-managed memory, see Chapter 2.3)
• Need a dynamic string? → use string The places you really hand-write new are mainly linked lists and binary trees that create nodes one by one (see the next section)—and even then, many competitors use array simulation or a static node pool to avoid new (see Chapters 5.5, 5.7).

2.7.7 The Killer Application of Pointers: Linked List and Tree Nodes

Where pointers are truly irreplaceable is in building data structures where nodes connect to each other. The most classic are linked lists and trees.

Singly Linked List Node

Each node is represented by a struct: holding data, plus a pointer to the next node.

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* next;   // pointer to the next node; the last node is nullptr
};

int main() {
    // Manually build 1 → 2 → 3
    Node* head = new Node{1, nullptr};
    head->next = new Node{2, nullptr};
    head->next->next = new Node{3, nullptr};

    // Traverse the list
    for (Node* cur = head; cur != nullptr; cur = cur->next) {
        cout << cur->data << " ";   // 1 2 3
    }
    cout << "\n";

    // Free (delete node by node from head to tail)
    while (head != nullptr) {
        Node* tmp = head;
        head = head->next;
        delete tmp;
    }

    return 0;
}

🤔 What is the cur->data syntax? cur is a pointer, and cur->data is equivalent to (*cur).data, meaning "follow the pointer to the node, then access its data member." -> is the dedicated "access member through pointer" operator, nicer than (*cur).data. This syntax appears everywhere in linked lists and trees.

Binary Tree Node

A tree is the natural extension of the linked-list idea—each node has not just one "next," but two child pointers, left and right:

struct TreeNode {
    int val;
    TreeNode* left;    // left child (nullptr if none)
    TreeNode* right;   // right child (nullptr if none)
};

// Create a node
TreeNode* root = new TreeNode{1, nullptr, nullptr};
root->left  = new TreeNode{2, nullptr, nullptr};
root->right = new TreeNode{3, nullptr, nullptr};

//        1
//       / \
//      2   3

🔗 Bridging ahead: The full algorithms for linked lists and trees (traversal, insertion, deletion, BST, balancing) are covered in detail in Chapter 5.5 (Binary Trees and Tree Algorithms). In this chapter you only need to understand the core mechanism of "how pointers string nodes together."

🆚 Pointer Version vs Array-Simulation Version (Contest Focus)

Competitors often avoid new and use array indices as "pointers"—this is called array simulation (static allocation / node pool). Building this comparison early makes Chapters 5.5/5.7 feel familiar:

// ---- Pointer version ----
struct Node { int v; Node* nxt; };
Node* head = new Node{1, nullptr};
head->nxt   = new Node{2, nullptr};

// ---- Array-simulation version (common in contests) ----
const int N = 100005;
int val[N], nxt[N], cnt = 0;   // index 0 reserved as "null"; real nodes start at 1
int head = 0;                  // 0 means empty list

int newNode(int v) {           // "new" a node → return its index
    ++cnt; val[cnt] = v; nxt[cnt] = 0; return cnt;
}
// Build 1 -> 2
head = newNode(1);
nxt[head] = newNode(2);

// Traverse: indices replace pointers, 0 replaces nullptr
for (int i = head; i != 0; i = nxt[i]) cout << val[i] << " ";

📌 Extension (just be aware): In production code, smart pointers unique_ptr / shared_ptr are commonly used to manage memory automatically (auto-delete when leaving scope, no leaks). But they are almost never used in contests—they add overhead, and a contest program reclaims memory on exit anyway. Just know they exist; in contests keep using raw pointers or array simulation.

2.7.8 const and Pointers: Read-Only Protection

When const combines with a pointer, different positions mean different things. This is a high-frequency topic in interviews and when reading source code:

int x = 10, y = 20;

const int* p1 = &x;   // pointer to const: cannot change value through p1, but can repoint
// *p1 = 99;  ❌ cannot change value
p1 = &y;              // ✓ can repoint

int* const p2 = &x;   // const pointer: can change value, but cannot repoint
*p2 = 99;             // ✓ can change value
// p2 = &y;  ❌ cannot repoint

const int* const p3 = &x;  // neither can change

💡 Reading mnemonic: Read right to left. const int* p reads as "p is a pointer to a const int"; int* const p reads as "p is a const pointer to an int." Whatever const is closest to is what it governs.

2.7.9 Multi-Level Pointers: Pointers to Pointers

A pointer itself is also a variable—it lives in some room in memory. So—a pointer also has an address. A pointer that points to another "pointer" is a multi-level pointer; the most common is the double pointer int**.

Why Do We Need Pointers to Pointers?

Three classic scenarios:

1. Modifying a pointer itself inside a function (e.g., making an int* parameter point to newly allocated memory)
2. Dynamic 2D arrays (int** points to an array of int*, each int* points to a row)
3. Command-line arguments argv (main's second parameter is char**)

#include <bits/stdc++.h>
using namespace std;

// Want a function to change an external pointer's target? Pass a double pointer!
void allocate(int** pp, int n) {
    *pp = new int[n];   // dereference the double pointer to modify the external pointer
}

int main() {
    int* arr = nullptr;
    allocate(&arr, 5);  // pass the address of arr (int**)
    for (int i = 0; i < 5; i++) arr[i] = i * i;
    for (int i = 0; i < 5; i++) cout << arr[i] << " ";
    cout << "\n";
    delete[] arr;
    return 0;
}

💡 You can also use a reference to a pointer (int*&) to achieve the same effect with cleaner syntax:

void allocate(int*& p, int n) { p = new int[n]; }

But double pointers are the lower-level understanding and a common pattern in legacy and low-level code.

Dynamic 2D Arrays

When both the number of rows and columns are known only at runtime, you can use int** to build a 2D array:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 3, m = 4;

    // Allocate n int* (row pointers)
    int** mat = new int*[n];
    for (int i = 0; i < n; i++) {
        mat[i] = new int[m];  // allocate m ints for each row
    }

    // Assign values
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            mat[i][j] = i * m + j;

    // Print
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cout << setw(3) << mat[i][j];
        cout << "\n";
    }

    // Free: free each row first, then the row-pointer array
    for (int i = 0; i < n; i++) delete[] mat[i];
    delete[] mat;

    return 0;
}

⚡ Contest tip: The int** 2D array above is almost never used in contests—it requires multiple new calls, memory is not contiguous (cache-unfriendly), and freeing is tedious. For dynamic 2D arrays in contests, always use vector<vector<int>> (see Chapter 2.3)—safe and concise. The double-pointer example here is mainly to build your mental picture of "pointer to pointer," so you can read low-level or legacy code.

Diagram: Double Pointer Hierarchy

📌 In one sentence: int x → int* p = &x (single-level pointer, points to a variable) → int** pp = &p (double pointer, points to a pointer). Each level of dereference * moves one step forward along the arrow: *pp gives p, **pp gives x.

2.7.10 Pointers and C-Style Strings

Before C++ was born, C used null-terminated (\0) character arrays to represent strings. These "C-style strings" have type char* or const char*. Although std::string is the absolute mainstream in modern C++, understanding char* helps with reading low-level code, contest templates, and deepening your pointer skills.

String Literals

const char* s = "hello";   // s points to the string literal "hello\0"
// s[0] = 'H';  ❌ String literals live in read-only memory—modifying is undefined behavior!

⚠️ The string literal "hello" has type const char[6] (including the trailing \0) and is stored in read-only memory. So you must use const char* to point to it. Old code may write char* s = "hello";—this is not recommended in modern C++ (and may not even compile).

Traversing C-Style Strings with Pointers

C-style strings end with \0, so you don't need the length to iterate:

#include <bits/stdc++.h>
using namespace std;

// Hand-written strlen: count until '\0'
int myStrlen(const char* s) {
    int len = 0;
    while (*s != '\0') {   // equivalent to while (*s)
        len++;
        s++;               // advance pointer to next character
    }
    return len;
}

// Hand-written strcpy: copy src into dst
void myStrcpy(char* dst, const char* src) {
    while (*src != '\0') {
        *dst = *src;       // copy character by character
        dst++;
        src++;
    }
    *dst = '\0';           // don't forget the trailing '\0'!
}

// More "pointer-ish" one-liner:
void myStrcpyV2(char* dst, const char* src) {
    while ((*dst++ = *src++));  // assign + check + advance, all in one
}

int main() {
    const char* s = "hello";
    cout << myStrlen(s) << "\n";  // 5

    char buf[100];
    myStrcpy(buf, s);
    cout << buf << "\n";          // hello

    return 0;
}

💡 The one-liner while ((*dst++ = *src++)); is a classic C-style pointer exercise. It compresses assignment, pointer advance, and condition check into a single line—the essence of pointer operations. If you're a beginner, work through the step-by-step version first, then come back to this one-liner—you'll find pointers much less mysterious.

C-Style Strings vs std::string

⚡ Contest iron rule: prefer std::string. Only deal with char* in main(int argc, char* argv[]) command-line arguments or when calling certain C library functions. The goal of this section is not to make you go back to C-style strings, but to let you read them when you see them.

2.7.11 Introduction to Function Pointers

In C++, functions also have addresses. A function pointer is a pointer that points to a function—you can pass "what operation to perform" just like passing data. This is the foundation of the callback mechanism.

Basic Syntax

Function pointer declarations have a distinctive syntax—you must wrap the * and the pointer name in parentheses:

// A function: takes two ints, returns a bool
bool cmp(int a, int b) { return a > b; }

// The corresponding function pointer type: bool (*)(int, int)
bool (*fp)(int, int) = cmp;   // fp points to cmp
//  ↑     ↑           ↑
// return  name(must have parentheses)  parameter type list

// Calling a function pointer: two equivalent ways
cout << fp(3, 5) << "\n";    // false (3 > 5)
cout << (*fp)(3, 5) << "\n"; // false (same, more explicit)

Typical Contest Application: Custom Sorting

std::sort's third argument is a function pointer (or function object):

#include <bits/stdc++.h>
using namespace std;

bool cmpAbs(int a, int b) {
    return abs(a) < abs(b);  // sort by ascending absolute value
}

int main() {
    vector<int> a = {-5, 3, -1, 4, -2};
    sort(a.begin(), a.end(), cmpAbs);  // cmpAbs passed as a function pointer
    for (int x : a) cout << x << " ";  // -1 -2 3 4 -5
    cout << "\n";
    return 0;
}

💡 In C++, lambda expressions or function objects (functors) are preferred over raw function pointers—they are more type-safe and easier for the compiler to inline. But function pointers are the foundation for understanding these advanced features—lambdas are essentially syntactic sugar over function pointers or function objects.

Function Pointer Arrays

When you need to dynamically choose among multiple operations, function pointer arrays are very handy:

int add(int a, int b) { return a + b; }
int sub(int a, int b) { return a - b; }
int mul(int a, int b) { return a * b; }

int (*ops[3])(int, int) = {add, sub, mul};  // array of function pointers

int op; cin >> op;
cout << ops[op](10, 5) << "\n";  // dynamically choose the operation

⚡ Contest tip: Function pointers are not commonly used in contests (often replaced by lambdas, std::function, or direct overloading), but they are essential knowledge for understanding callbacks, event-driven programming, and C standard library functions like qsort. Know they exist; no need to go deep.

⚠️ Chapter 2.7 Common Mistakes

Chapter Summary

📌 Key Takeaways

❓ Frequently Asked Questions

Q1: Pointers are so dangerous—are they still worth learning for contests?

A: Yes, but keep priorities straight. For 90% of problems, vector, string, and references are enough—no raw pointers needed. But when you reach linked lists, binary trees, the "chained forward star" graph representation, or read others' template code, you cannot move an inch without understanding pointers. The goal of this chapter is to let you "read and use them correctly," not to hand-write new everywhere.

Q2: Reference or pointer—which should I prefer?

A: Prefer references. To avoid copies when passing parameters → use const T&; to modify the original variable → use T&. Only when "the target changes" (traversing a linked list), "there might be no target" (a tree's empty child nullptr), or "dynamic allocation" (new) do you need pointers.

Q3: I keep mixing up *p, &x, and p->m. What do I do?

A: Remember three phrases: &x is "where x lives" (address-of); *p is "follow p to look at that room" (dereference); p->m is "follow p to the struct, then access its member m." Write out linked-list traversal a few times and the muscle memory forms.

Q4: Do I really have to manually delete in contests? Will I lose points if I forget?

A: Usually not. When the program ends, the OS auto-reclaims all memory, so memory leaks in contests are generally harmless. What you really need to watch is repeated new during execution causing MLE (memory limit exceeded)—which is rare. Conclusion: use vector/string instead of manual memory management whenever you can.

Here is a counter-example that triggers MLE—repeatedly new inside a big loop without ever delete:

// ❌ Dangerous: allocate on the heap every iteration, never free
for (int i = 0; i < 10000000; i++) {
    int* p = new int[1000];   // 4KB each time, ~40 GB total → MLE!
    // ... done with p but forgot delete[] p;
}
// ✅ Fix: either allocate once outside the loop and reuse, or delete[] p; after use,
//         safest is just vector<int> p(1000); (auto-reclaimed when leaving scope)

Q5: Why do some competitors' tree/linked-list code use no pointers at all?

A: They use array simulation (also called static allocation / a node pool): three arrays int left[N], right[N], val[N]; serve as nodes, with indices acting as "pointers." This is faster, less error-prone, and avoids new's overhead—the mainstream approach in contests (see Chapters 5.5, 5.7). Understand the pointer version first, and the array version becomes clearer.

Q6: Do I really need multi-level pointers and function pointers in contests?

A: You won't write them often, but understanding them greatly improves your code-reading ability. Double pointers help you understand argv (command-line arguments) and the low-level of dynamic 2D arrays; function pointers help you understand sort's custom comparator and qsort callbacks. More importantly, these concepts are the foundation for later advanced features like STL function objects and lambda expressions. In one sentence: you don't have to write them every day, but you cannot afford to be unable to read them.

🔗 Connections to Later Chapters

• Chapter 5.5 (Binary Trees and Tree Algorithms): the TreeNode struct here is the starting point for tree traversal and BSTs
• Chapter 5.6 (Union-Find), Chapter 5.7 (Segment Trees): you will see the trade-offs between the "pointer version" and the "array-simulation version"
• Chapter 5.1 (Introduction to Graphs): the chained forward star essentially uses arrays to simulate a linked list to store a graph
• The "memory and address" mental model built here deepens your understanding of vector resizing, string internals, and reference parameter passing

Practice Problems

🌡️ Warm-Up Problems

Warm-Up 2.7.1 — Modify Through a Pointer Declare int x = 5;, define a pointer p to x, change x to 99 through *p, then print x.

Expected output: 99

#include <bits/stdc++.h>
using namespace std;

int main() {
    int x = 5;
    int* p = &x;    // p points to x
    *p = 99;        // modify x through the pointer
    cout << x << "\n";  // 99
    return 0;
}

Warm-Up 2.7.2 — Pointer Swap Write a function void swp(int* a, int* b) that swaps two variables using pointers. In main, read two integers, swap them, and print.

Sample input: 3 7 → Sample output: 7 3

#include <bits/stdc++.h>
using namespace std;

void swp(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int main() {
    int x, y;
    cin >> x >> y;
    swp(&x, &y);    // remember to pass addresses
    cout << x << " " << y << "\n";
    return 0;
}

Warm-Up 2.7.3 — Arrays and Pointers Declare int arr[5] = {10,20,30,40,50};, define a pointer p = arr, and print the third element using *(p+2).

Expected output: 30

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[5] = {10, 20, 30, 40, 50};
    int* p = arr;           // the array name decays to a first-element pointer
    cout << *(p + 2) << "\n";  // 30, equivalent to arr[2]
    return 0;
}

🏋️ Core Problems

Problem 2.7.4 — Find the Max and Return a Pointer Read N integers into an array, write a function that returns a pointer to the maximum element, and in main print the max through that pointer.

Sample input:

5
3 9 2 9 4

Sample output: 9

#include <bits/stdc++.h>
using namespace std;

int* findMax(int* arr, int n) {
    int* best = arr;        // assume the first is the max
    for (int i = 1; i < n; i++) {
        if (arr[i] > *best) best = &arr[i];
    }
    return best;            // return a pointer to the max element
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int* p = findMax(a.data(), n);  // a.data() gives the underlying array pointer
    cout << *p << "\n";
    return 0;
}

Problem 2.7.5 — Reverse an Array In Place Using Pointers Read N integers and reverse the array in place using two pointers (one from the front, one from the back), then print.

Sample input:

5
1 2 3 4 5

Sample output: 5 4 3 2 1

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int* left = &a[0];
    int* right = &a[n - 1];
    while (left < right) {       // pointers can be compared directly
        swap(*left, *right);
        left++;
        right--;
    }

    for (int x : a) cout << x << " ";
    cout << "\n";
    return 0;
}

Problem 2.7.6 — Hand-Written Linked List Sum Without vector, use struct Node{int data; Node* next;} to manually build a linked list of N integers, traverse to compute the sum, and print it.

Sample input:

4
10 20 30 40

Sample output: 100

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* next;
};

int main() {
    int n;
    cin >> n;

    Node* head = nullptr;
    Node* tail = nullptr;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        Node* node = new Node{x, nullptr};
        if (head == nullptr) {      // the first node
            head = tail = node;
        } else {
            tail->next = node;      // attach to the tail
            tail = node;            // update the tail pointer
        }
    }

    long long sum = 0;
    for (Node* cur = head; cur != nullptr; cur = cur->next) {
        sum += cur->data;
    }
    cout << sum << "\n";

    // free
    while (head) { Node* t = head; head = head->next; delete t; }

    return 0;
}

🏆 Challenge Problems

Challenge 2.7.7 — Reverse a Linked List (Classic interview & contest fundamental)

Build a linked list 1→2→3→4→5, reverse it into 5→4→3→2→1, then print it. Use only pointer operations, no arrays.

Expected output: 5 4 3 2 1

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* next;
};

int main() {
    // Build 1→2→3→4→5
    Node* head = nullptr;
    for (int i = 5; i >= 1; i--) {   // head-insert in reverse to get ascending order
        head = new Node{i, head};
    }

    // Reverse
    Node* prev = nullptr;
    Node* cur = head;
    while (cur != nullptr) {
        Node* next = cur->next;  // 1. save the next node first
        cur->next = prev;        // 2. point the current node back to prev
        prev = cur;              // 3. advance prev
        cur = next;              // 4. advance cur
    }
    head = prev;                 // prev becomes the new head

    // Print
    for (Node* p = head; p; p = p->next) cout << p->data << " ";
    cout << "\n";

    return 0;
}

Challenge 2.7.8 — Detect a Cycle in a Linked List (Classic fast-slow pointer application)

Given a possibly cyclic linked list, determine whether it has a cycle. Print YES or NO.

Hint: Use "fast-slow pointers"—the slow pointer moves 1 step at a time, the fast pointer 2 steps. If they meet, there is a cycle (this is Floyd's cycle-finding algorithm).

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* next;
};

bool hasCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;          // slow: 1 step
        fast = fast->next->next;    // fast: 2 steps
        if (slow == fast) return true;  // they meet → cycle
    }
    return false;   // fast reached the end → no cycle
}

int main() {
    // Build 1→2→3→4, then make 4 point back to 2 to form a cycle
    Node* n1 = new Node{1, nullptr};
    Node* n2 = new Node{2, nullptr};
    Node* n3 = new Node{3, nullptr};
    Node* n4 = new Node{4, nullptr};
    n1->next = n2; n2->next = n3; n3->next = n4;
    n4->next = n2;   // create a cycle!

    cout << (hasCycle(n1) ? "YES" : "NO") << "\n";  // YES
    return 0;
}

Challenge 2.7.9 — Cows Lining Up (USACO Bronze style) (Simulate dynamic queue-jumping with a linked list + pointers)

Farmer John's N cows line up in a queue (numbered 1..N, front to back). Then M events occur, each of the form x y: cow number x cuts in directly behind cow number y (x and y differ; x is currently in the queue and is first removed from its old spot, then inserted). After all events, print the whole queue from front to back.

Sample input:

4 2
2 4
1 3

(initial queue 1 2 3 4; event 1: 2 behind 4 → 1 3 4 2; event 2: 1 behind 3 → 3 1 4 2)

Sample output: 3 1 4 2

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int pre[N], nxt[N];   // pre[i]/nxt[i]: predecessor/successor of number i; 0 is the sentinel

void detach(int x) {          // detach x from its current position
    nxt[pre[x]] = nxt[x];
    pre[nxt[x]] = pre[x];
}
void insertAfter(int y, int x) {  // insert x directly behind y
    int z = nxt[y];           // y's original successor
    nxt[y] = x; pre[x] = y;
    nxt[x] = z; pre[z] = x;
}

int main() {
    int n, m;
    cin >> n >> m;

    // initial queue 1 2 ... n, stitched at both ends with sentinel 0
    pre[1] = 0; nxt[0] = 1;       // 0 → 1
    for (int i = 1; i < n; i++) { nxt[i] = i + 1; pre[i + 1] = i; }
    nxt[n] = 0; pre[0] = n;       // n → 0 (back to sentinel = end of queue)

    while (m--) {
        int x, y;
        cin >> x >> y;
        detach(x);            // first remove x from its old spot
        insertAfter(y, x);    // then insert it behind y
    }

    // start at the first node after the sentinel, follow nxt to print the queue
    for (int i = nxt[0]; i != 0; i = nxt[i]) {
        cout << i << (nxt[i] ? " " : "\n");
    }
    return 0;
}

Problem 2.7.10 — Hand-Write myStrlen with Pointers (Classic exercise in traversing C-style strings with pointers)

Without using any library functions, implement int myStrlen(const char* s) using pure pointer operations. Return the string length (excluding \0). Test in main.

Expected output (input "hello"): 5

#include <bits/stdc++.h>
using namespace std;

int myStrlen(const char* s) {
    int len = 0;
    while (*s != '\0') {  // equivalent to while (*s)
        len++;
        s++;              // advance pointer to next character
    }
    return len;
}

int main() {
    const char* s = "hello";
    cout << myStrlen(s) << "\n";  // 5
    return 0;
}

Problem 2.7.11 — Hand-Write myStrcpy with Pointers (Classic exercise in pointer-based assignment)

Without using any library functions, implement void myStrcpy(char* dst, const char* src) using pure pointer operations. Copy the string pointed to by src into dst. Test in main.

Expected output (input "world"): world

#include <bits/stdc++.h>
using namespace std;

void myStrcpy(char* dst, const char* src) {
    while (*src != '\0') {
        *dst = *src;   // copy character by character
        dst++;
        src++;
    }
    *dst = '\0';       // don't forget the trailing '\0'!
}

// Compact version (read after understanding the principle):
void myStrcpyV2(char* dst, const char* src) {
    while ((*dst++ = *src++));  // assign + check + advance, all in one
}

int main() {
    const char* src = "world";
    char dst[100];
    myStrcpy(dst, src);
    cout << dst << "\n";  // world
    return 0;
}

Problem 2.7.12 — Merge Two Sorted Linked Lists (Classic pointer operation, high-frequency interview problem)

Given two ascending linked lists L1 and L2, merge them into a single ascending linked list and return the head pointer. Only modify pointers—do not create new nodes (no new).

Sample input (two lists): 1→3→5 and 2→4→6 Sample output: 1 2 3 4 5 6

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* next;
};

Node* mergeTwoLists(Node* l1, Node* l2) {
    Node dummy{0, nullptr};       // dummy node simplifies head handling
    Node* tail = &dummy;          // tail always points to the end of the result list

    while (l1 != nullptr && l2 != nullptr) {
        if (l1->data < l2->data) {
            tail->next = l1;      // detach l1's current node
            l1 = l1->next;        // advance l1
        } else {
            tail->next = l2;      // detach l2's current node
            l2 = l2->next;        // advance l2
        }
        tail = tail->next;        // tail stays at the end
    }

    // Attach the remaining list (at most one is non-empty)
    tail->next = (l1 != nullptr) ? l1 : l2;

    return dummy.next;            // skip the dummy, return the real head
}

int main() {
    // Build L1: 1→3→5
    Node* l1 = new Node{1, new Node{3, new Node{5, nullptr}}};
    // Build L2: 2→4→6
    Node* l2 = new Node{2, new Node{4, new Node{6, nullptr}}};

    Node* merged = mergeTwoLists(l1, l2);

    for (Node* p = merged; p; p = p->next)
        cout << p->data << " ";
    cout << "\n";  // 1 2 3 4 5 6

    return 0;
}

Problem 2.7.13 — Find the Middle of a Linked List (Another classic fast-slow pointer application)

Given a singly linked list, use fast-slow pointers to find its middle node. If the length is even, return the second middle node.

Sample input: 1→2→3→4→5 Sample output: 3 (the 3rd node is the middle)

Sample input: 1→2→3→4 Sample output: 3 (even length, return the second of the two middles)

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* next;
};

Node* findMiddle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;          // slow: 1 step
        fast = fast->next->next;    // fast: 2 steps
    }
    return slow;  // when fast reaches the end, slow is at the middle
}

int main() {
    // Test 1: 1→2→3→4→5 (odd)
    Node* head1 = new Node{1, new Node{2, new Node{3,
                        new Node{4, new Node{5, nullptr}}}}};
    cout << findMiddle(head1)->data << "\n";  // 3

    // Test 2: 1→2→3→4 (even)
    Node* head2 = new Node{1, new Node{2, new Node{3,
                        new Node{4, nullptr}}}};
    cout << findMiddle(head2)->data << "\n";  // 3

    return 0;
}

🔗 USACO Practice Problems

The pointer / linked-list ideas in this chapter map directly to the following official USACO problems. Try implementing them with this chapter's "pointer version" or "array-simulation version" first, then submit on usaco.org to verify:

💡 Solving hints:

• Reordering the Cows: each cow must travel from position i to its target; following "where this cow should go, and where the cow originally there should go" traces out one or more "cycles." This "hop along the pointers" traversal is the same mindset as linked-list traversal and Floyd's cycle finding.
• Cow Line: both ends need O(1) insert/remove—the standard tool is a deque. Having understood this chapter's doubly linked list (the pre / nxt "pointers" in both directions), you can see why a deque achieves O(1) at both ends internally.

📌 A more systematic problem list: USACO Guide organizes official problems by difficulty and topic (including Stacks/Queues and Linked Lists)—an authoritative roadmap for pre-contest practice.