Array Manipulation

Merge Sorted Arrays In-Place

Given two integer arrays sorted in non-decreasing order, combine them into a single sorted sequence stored inside the first array. The first array has enough trailing buffer (initialized to zero) to hold all elements from the second array.

Start filling from the rear of the buffer. Compare the current elements of both arrays and place the larger value at the write position, then expand the corresponding boundary inward.

void merge(int* buffer, int totalLen, int m, int* incoming, int incomingLen, int n) {
    int writePos = totalLen - 1;
    int idx1 = m - 1;
    int idx2 = n - 1;

    while (idx1 >= 0 && idx2 >= 0) {
        if (buffer[idx1] > incoming[idx2]) {
            buffer[writePos--] = buffer[idx1--];
        } else {
            buffer[writePos--] = incoming[idx2--];
        }
    }

    while (idx2 >= 0) {
        buffer[writePos--] = incoming[idx2--];
    }
}

Remove All Occurrences of a Value

Given an array and a target value, eliminate every instance of that value in-place using O(1) extra space. The realtive order of remaining elements may change, and elements beyond the new length are ignored.

Maintain a write cursor. Iterate through the array with a read cursor, copying values that differ from the target forward.

int removeTarget(int* nums, int len, int target) {
    if (!nums || len <= 0) return 0;

    int writer = 0;
    for (int reader = 0; reader < len; reader++) {
        if (nums[reader] != target) {
            nums[writer++] = nums[reader];
        }
    }
    return writer;
}

Linked List Manipulation

Eliminate Nodes by Value

Given the head of a linked list and an integer, delete every node whose data equals that integer and return the new head.

Introduce a dummy head node to simplify deletion at the front. Traverse the list once, appending valid nodes to a new tail and skipping matches.

typedef struct ListNode Node;

struct ListNode* deleteValue(struct ListNode* head, int val) {
    Node dummy;
    Node* tail = &dummy;
    Node* current = head;

    while (current) {
        if (current->val != val) {
            tail->next = current;
            tail = current;
        }
        current = current->next;
    }
    tail->next = NULL;
    return dummy.next;
}

Iterative List Reversal

Reverse the direction of all pointers in a singly linked list and return the node that originally occupied the tail position.

Track three positions: the node already reversed, the node being processed, and the next candidate. Rewire the current node's successor to point backward, then advance all three markers.

typedef struct ListNode Node;

struct ListNode* reverse(struct ListNode* head) {
    Node* previous = NULL;
    Node* current = head;

    while (current) {
        Node* upcoming = current->next;
        current->next = previous;
        previous = current;
        current = upcoming;
    }
    return previous;
}

Merge Two Ascending Lists

Combine two sorted linked lists into a new list where node values continue to appear in ascending order.

Anchor a dummy node to avoid special-casing the initial insertion. Repeated attach the smaller front node between the two lists, advancing that list's pointer. When one list empties, splice the remainder directly.

typedef struct ListNode Node;

struct ListNode* mergeSorted(struct ListNode* a, struct ListNode* b) {
    Node anchor;
    Node* tail = &anchor;
    Node* p = a;
    Node* q = b;

    while (p && q) {
        if (p->val < q->val) {
            tail->next = p;
            p = p->next;
        } else {
            tail->next = q;
            q = q->next;
        }
        tail = tail->next;
    }

    tail->next = p ? p : q;
    return anchor.next;
}

Detect the Middle Node

Return the middle node of a singly linked list. If there are two central nodes, return the second one.

Advance a slow pointer one step at a time while a fast pointer advances two steps. When the fast pointer reaches the end, the slow pointer rests on the desired middle node.

typedef struct ListNode Node;

struct ListNode* getMiddle(struct ListNode* head) {
    Node* walker = head;
    Node* runner = head;

    while (runner && runner->next) {
        walker = walker->next;
        runner = runner->next->next;
    }
    return walker;
}

Josephus Problem via Circular List

n people stand in a circle numbered from 1 to n. Counting starts at 1 and proceeds clockwise; every person who reaches count m is removed. Determine the number of the last remaining person.

Model the circle as a circular linked list. Traverse while removing nodes at the m-th count until one node remains.

typedef struct ListNode Node;

Node* createRingNode(int value) {
    Node* n = (Node*)malloc(sizeof(Node));
    if (!n) exit(1);
    n->val = value;
    n->next = NULL;
    return n;
}

Node* buildCircle(int n) {
    Node* first = createRingNode(1);
    Node* tail = first;
    for (int i = 2; i <= n; i++) {
        tail->next = createRingNode(i);
        tail = tail->next;
    }
    tail->next = first;
    return tail;
}

int josephus(int n, int m) {
    if (n <= 0) return -1;

    Node* prev = buildCircle(n);
    Node* curr = prev->next;
    int count = 1;

    while (curr->next != curr) {
        if (count == m) {
            prev->next = curr->next;
            free(curr);
            curr = prev->next;
            count = 1;
        } else {
            prev = curr;
            curr = curr->next;
            count++;
        }
    }

    int survivor = curr->val;
    free(curr);
    return survivor;
}

Partition Around a Pivot

Reorder a linked list so that all nodes with values strictly less than x appear before nodes with values greater than or equal to x. Original relative order within each partition need not be preserved.

Maintain two separate chains: one for values below the pivot and one for values at or above it. After traversal, concatenate the two chains.

typedef struct ListNode Node;

struct ListNode* partition(struct ListNode* head, int x) {
    if (!head) return NULL;

    Node lowSentinel, highSentinel;
    lowSentinel.next = NULL;
    highSentinel.next = NULL;
    Node* lowTail = &lowSentinel;
    Node* highTail = &highSentinel;
    Node* current = head;

    while (current) {
        if (current->val < x) {
            lowTail->next = current;
            lowTail = current;
        } else {
            highTail->next = current;
            highTail = current;
        }
        current = current->next;
    }

    highTail->next = NULL;
    lowTail->next = highSentinel.next;
    return lowSentinel.next;
}