LeetCode 54: Spiral Matrix

Problem

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,3,6,9,8,7,4,5]

Example 2

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Approach

1. Traverse from left to right along the top row: (top, left) to (top, right).
2. Traverse from top to bottom along the right column: (top+1, right) to (bottom, right).
3. If left < right and top < bottom, traverse from right to left along the bottom row: (bottom, right-1) to (bottom, left+1), and from bottom to top along the left column: (bottom, left) to (top+1, left).
4. After finishing a layer, increment left and top, decrement right and bottom, and continue until all elements are proecssed.

Solution Code

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {
    if (matrixSize == 0 || matrixColSize[0] == 0) {
        *returnSize = 0;
        return NULL;
    }
    int total = matrixSize * matrixColSize[0];
    int* result = (int*)malloc(sizeof(int) * total);
    int top = 0, bottom = matrixSize - 1;
    int left = 0, right = matrixColSize[0] - 1;
    int index = 0;
    while (left <= right && top <= bottom) {
        for (int col = left; col <= right; col++) {
            result[index++] = matrix[top][col];
        }
        for (int row = top + 1; row <= bottom; row++) {
            result[index++] = matrix[row][right];
        }
        if (left < right && top < bottom) {
            for (int col = right - 1; col > left; col--) {
                result[index++] = matrix[bottom][col];
            }
            for (int row = bottom; row > top; row--) {
                result[index++] = matrix[row][left];
            }
        }
        left++;
        right--;
        top++;
        bottom--;
    }
    *returnSize = index;
    return result;
}

LeetCode 445: Add Two Numbers II

Problem

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first, and each node contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1

Input: l1 = [7,2,4,3], l2 = [5,6,4] Output: [7,8,0,7]

Example 2

Input: l1 = [2,4,3], l2 = [5,6,4] Output: [8,0,7]

Example 3

Input: l1 = [0], l2 = [0] Output: [0]

Approach

1. Reverse both linked lists l1 and l2 to simulate addition from least significant digit.
2. Create a dummy head node and use tail insertion to store the sum of corresponding digits, handling carry.
3. After processing all digits, reverse the resulting list to restore original order.

Solution Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverse(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    while (curr) {
        struct ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* rev1 = reverse(l1);
    struct ListNode* rev2 = reverse(l2);

    struct ListNode dummy;
    dummy.next = NULL;
    struct ListNode* tail = &dummy;

    int carry = 0;
    while (rev1 || rev2 || carry) {
        int x = rev1 ? rev1->val : 0;
        int y = rev2 ? rev2->val : 0;
        int sum = x + y + carry;
        carry = sum / 10;

        tail->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        tail->next->val = sum % 10;
        tail->next->next = NULL;
        tail = tail->next;

        if (rev1) rev1 = rev1->next;
        if (rev2) rev2 = rev2->next;
    }

    struct ListNode* result = reverse(dummy.next);
    return result;
}