This review focuses on core techniques for arrays and linked lists, including practical C++ implementations.

Arrays

The most important concept for array problems is the two-pointer technique.

Fast and Slow Pointers

When removing or manipulating elements, nested loops lead to O(n²) time complexity. Using two pointers (a slow and a fast pointer) reduces this to O(n).

int slowIndex = 0;
int fastIndex = 0;
for (fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
    // logic here
}

Opposite Direction Pointers

For element removal where order can change, opposite direction pointers minimize the number of moves.

int leftIndex = 0;
int rightIndex = nums.size() - 1;

while (leftIndex <= rightIndex) {
    while (leftIndex <= rightIndex && nums[leftIndex] != val) {
        ++leftIndex;
    }
    while (rightIndex >= leftIndex && nums[rightIndex] == val) {
        --rightIndex;
    }
    if (leftIndex < rightIndex) {
        nums[leftIndex++] = nums[rightIndex--];
    }
}

Sliding Window

When the focus is on the sum of elements between two pointers, it becomes a sliding window problem. The key is managing the start and end positions of the window.

while (sum >= s) {
    subLength = (j - i + 1);
    result = result < subLength ? result : subLength;
    sum -= nums[i++];
}

The ternary operator c = a < b ? a : b assigns the smaller of a and b to c. It is equivalent to:

if (a < b) {
    c = a;
} else {
    c = b;
}

Spiral Matrix

Spiral matrix generation requires four loops following the loop invariant principle. An outer while loop controls each layer, and inner for loops assign values to rows and columns with a left-closed, right-open interval.

Linked Lists

A linked list is a linear structure where nodes are connected via pointers. Each node has a data field and a pointer field.

Designing a Linked List

Defining a node struct:

struct LinkedNode {
    int val;
    LinkedNode* next;
    LinkedNode(int val) : val(val), next(nullptr) {}
};

Initializing the linked list:

MyLinkedList() {
    _dummyNode = new LinkedNode(0);
    _size = 0;
}

Retrieving the value at index index (0‑based):

int get(int index) {
    if (index > (_size - 1) || index < 0) {
        return -1;
    }
    LinkedNode* cur = _dummyHead->next;
    while (index--) {
        cur = cur->next;
    }
    return cur->val;
}

Inserting at head:

void addAtHead(int val) {
    LinkedNode* newNode = new LinkedNode(val);
    newNode->next = _dummyHead->next;
    _dummyHead->next = newNode;
    _size++;
}

Inserting at tail:

void addAtTail(int val) {
    LinkedNode* newNode = new LinkedNode(val);
    newNode->next = _dummyHead->next;
    _dummyHead->next = newNode;
    _size++;
}

Inserting before the node at index index:

void addAtIndex(int index, int val) {
    if (index > _size) return;
    if (index < 0) index = 0;
    LinkedNode* newNode = new LinkedNode(val);
    LinkedNode* cur = _dummyHead;
    while (index--) {
        cur = cur->next;
    }
    newNode->next = cur->next;
    cur->next = newNode;
    _size++;
}

Deleting the node at index index:

void deleteAtIndex(int index) {
    if (index >= _size || index < 0) {
        return;
    }
    LinkedNode* cur = _dummyHead;
    while (index--) {
        cur = cur->next;
    }
    LinkedNode* tmp = cur->next;
    cur->next = cur->next->next;
    delete tmp;
    _size--;
}

Printing the linked list:

void printLinkedList() {
    LinkedNode* cur = _dummyHead;
    while (cur->next != nullptr) {
        cout << cur->next->val << " ";
        cur = cur->next;
    }
    cout << endl;
}

Dummy Head Node

A dummy head node simplifies operations, especially deletions.

ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;

Node Field Nottaion

• head->val – value of the head node.
• head->next – pointer to the next node.
• head->next->next – the node two positions after the head.

C++ Basics

• swap(a, b) swaps the values of a and b. Typically O(1) for built‑in types.
• Ternary operator: c = a < b ? a : b;
• Basic template:

#include <iostream>
using namespace std;
int main() {}

• Vector container for dynamic arrays:

#include <vector>
using namespace std;
int main() {
    vector<int>& a;
}