LeetCode Hot 100 精选：C 语言实现与思路解析（1-21）

21. 合并两个有序链表

将两个升序链表合并为一个新的升序链表。

分析：递归写法很简洁，但尾插法更直观且节省栈空间。通过比较节点值，依次连接较小的节点到结果链表中。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode dummy;
    struct ListNode *p=&dummy;
    while(list1!=NULL && list2!=NULL) {
        if(list1->val<=list2->val) {
            p->next=list1;
            list1=list1->next;
        } else {
            p->next=list2;
            list2=list2->next;
        }
        p=p->next;
    }
    p->next=list1?list1:list2;
    return dummy.next;
}

70. 爬楼梯

每次可以爬 1 或 2 个台阶，求 n 阶有多少种方法。

分析：本质是斐波那契数列。用迭代代替递归可以避免重复计算，空间复杂度降为 O(1)。

int climbStairs(int n) {
    if (n <= 2) return n;
    int prev2 = 1; // f(n-2)
    int prev1 = 2; // f(n-1)
    int curr;
    for (int i = 3; i <= n; i++) {
        curr = prev1 + prev2; // f(n) = f(n-1) + f(n-2)
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

94. 二叉树的中序遍历

返回二叉树的中序遍历结果。

分析：中序即'左根右'。递归实现最简单，注意指针操作时的优先级问题，比如 (*returnSize)++ 必须加括号。

void inorder(struct TreeNode* root, int* tree, int* returnSize) {
    if(root == NULL) { return; }
    inorder(root->left, tree, returnSize); // 左
    tree[*returnSize] = root->val;         // 根
    (*returnSize)++;                       // 括号包裹
    inorder(root->right, tree, returnSize); // 右
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    int *tree = malloc(sizeof(int) * 300);
    inorder(root, tree, returnSize);
    return tree;
}

101. 对称二叉树

检查二叉树是否轴对称。

分析：递归判断左右子树是否镜像。核心逻辑是：左的左 vs 右的右，左的右 vs 右的左。

bool judge(struct TreeNode* left, struct TreeNode* right) {
    if(right==NULL && left==NULL){return true;}
    if(right==NULL || left==NULL){return false;}
    if(right->val != left->val){return false;}
    return judge(left->left,right->right) && judge(left->right,right->left);
}

bool isSymmetric(struct TreeNode* root) {
    if(root == NULL) { return true; }
    return judge(root,root);
}

104. 二叉树的最大深度

返回从根节点到最远叶子节点的最长路径上的节点数。

分析：最大深度等于左右子树最大深度的较大者加 1。递归终止条件是节点为空。

int maxDepth(struct TreeNode* root) {
    if (root == NULL) { return 0; }
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}

121. 买卖股票的最佳时机

只能选择某一天买入并在未来卖出，计算最大利润。

分析：维护一个历史最低点 buy，每天计算当前价格与最低点的差值作为潜在利润，取最大值即可。

int maxProfit(int* prices, int pricesSize) {
    int buy = prices[0];
    int money = 0;
    for(int i=0;i<pricesSize;i++) {
        if(prices[i]-buy>money){money=prices[i]-buy;}
        if(prices[i]<buy){buy=prices[i];}
    }
    return money;
}

136. 只出现一次的数字

除某个元素外其余均出现两次，找出该元素。

分析：官方最优解是利用异或运算的性质：a ^ a = 0, a ^ 0 = a。成对的数会抵消，最后剩下唯一的数。哈希表方案虽可行但占用额外空间。

// 异或解法（推荐）
int singleNumber(int* nums, int numsSize) {
    int result = 0;
    for(int i = 0; i < numsSize; i++) {
        result ^= nums[i]; // 成对的数会抵消，只剩单个的
    }
    return result;
}

// 哈希表解法（备选）
#define OFFSET 30000
#define SIZE 60001
int singleNumberHash(int* nums, int numsSize) {
    int hash[SIZE] = {0};
    for(int i = 0; i < numsSize; i++) {
        int idx = nums[i] + OFFSET;
        hash[idx] ^= 1;
    }
    for(int i = 0; i < SIZE; i++) {
        if(hash[i] == 1) { return i - OFFSET; }
    }
    return 0;
}

141. 环形链表

判断链表中是否有环。

分析：快慢指针法。如果存在环，快指针最终会追上慢指针。

bool hasCycle(struct ListNode *head) {
    struct ListNode *fast=head;
    struct ListNode *slow=head;
    while(fast!=NULL && fast->next!=NULL) {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow) { return true; }
    }
    return false;
}

160. 相交链表

找出两个单链表相交的起始节点。

分析：双指针技巧非常优雅。让两个指针分别遍历完自己的链表后转向另一条链表，若相交必在交点相遇；若不相交则在终点相遇（均为 NULL）。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if (headA == NULL || headB == NULL) return NULL;
    struct ListNode *pA = headA, *pB = headB;
    while (pA != pB) {
        pA = (pA == NULL) ? headB : pA->next;
        pB = (pB == NULL) ? headA : pB->next;
    }
    return pA;
}

169. 多数元素

数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

分析：摩尔投票法。不同元素'一命抵一命'，最后剩下的候选人即为多数元素。

int majorityElement(int* nums, int numsSize) {
    int a=nums[0];
    int blood=1;
    for(int i=1;i<numsSize;i++) {
        int b=nums[i];
        if(a==b) { blood++; }
        else {
            blood--;
            if(blood<0) { a=nums[i]; blood=0; }
        }
    }
    return a;
}

206. 翻转链表

反转链表并返回新头节点。

分析：原地反转只需修改指针指向。头插法也可以生成新链表，但不推荐因为涉及多次内存分配。

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *prev = NULL;
    struct ListNode *curr = head;
    struct ListNode *next = NULL;
    while (curr != NULL) {
        next = curr->next;      // 保存下一个节点
        curr->next = prev;      // 反转当前节点指向
        prev = curr;            // prev 前移
        curr = next;            // curr 前移
    }
    return prev; // 新头节点
}

226. 翻转二叉树

翻转这棵二叉树，交换所有节点的左右子树。

分析：经典的递归问题。先递归翻转左右子树，再交换当前节点的左右指针。

struct TreeNode* invertTree(struct TreeNode* root) {
    if (root == NULL) { return NULL; }
    struct TreeNode* left = invertTree(root->left);
    struct TreeNode* right = invertTree(root->right);
    root->left = right;
    root->right = left;
    return root;
}

234. 回文链表

判断链表是否为回文结构。

分析：最佳实践是快慢指针找中点，反转后半部分，然后比对。完成后记得恢复链表结构。

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *prev = NULL, *cur = head;
    while (cur) {
        struct ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

bool isPalindrome(struct ListNode* head) {
    if (head == NULL || head->next == NULL) return true;
    struct ListNode *slow = head, *fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    struct ListNode* secondHalfStart = reverseList(slow->next);
    struct ListNode *firstHalfStart = head;
    struct ListNode *secondHalfCopy = secondHalfStart;
    bool result = true;
    while (secondHalfStart) {
        if (firstHalfStart->val != secondHalfStart->val) {
            result = false;
            break;
        }
        firstHalfStart = firstHalfStart->next;
        secondHalfStart = secondHalfStart->next;
    }
    slow->next = reverseList(secondHalfCopy);
    return result;
}

283. 移动零

将所有 0 移动到末尾，保持非零元素相对顺序。

分析：记录前面有多少个零，遇到非零元素就向前交换位置，避免多余拷贝。

void moveZeroes(int* nums, int numsSize) {
    int cnt=0;
    for(int i=0;i<numsSize;i++) {
        if(nums[i]==0) {
            cnt++;
        } else {
            int temp=nums[i-cnt];
            nums[i-cnt]=nums[i];
            nums[i]=temp;
        }
    }
}

338. 比特位计数

计算 0 到 n 每个数的二进制中 1 的个数。

分析：Brian Kernighan 算法利用 x & (x - 1) 消除最低位的 1，效率高于除二取余。

int countOnes(int x) {
    int ones = 0;
    while (x > 0) {
        x &= (x - 1);
        ones++;
    }
    return ones;
}

int* countBits(int n, int* returnSize) {
    int*a=malloc(sizeof(int)*(n+1));
    *returnSize=n+1;
    for (int i = 0; i <= n; i++) {
        a[i] = countOnes(i);
    }
    return a;
}

448. 找到所有数组中消失的数字

找出 [1, n] 范围内未出现在数组中的数字。

分析：利用数组本身作为哈希表。将访问到的数字对应索引处的值标记为负数，最后正数对应的索引即为缺失数字。

int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) {
    for (int i = 0; i < numsSize; i++) {
        int index = abs(nums[i]) - 1;
        if (nums[index] > 0) {
            nums[index] = -nums[index];
        }
    }
    int* result = malloc(sizeof(int) * numsSize);
    int count = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > 0) {
            result[count++] = i + 1;
        }
    }
    *returnSize = count;
    return result;
}

461. 汉明距离

计算两个整数二进制位不同的位置数目。

分析：先异或得到不同位，再用 Brian Kernighan 算法统计 1 的个数。GCC 编译器提供内置函数 __builtin_popcount 可直接使用。

int hammingDistance(int x, int y) {
    unsigned int xor = x ^ y;
    int count = 0;
    while (xor) {
        xor &= xor - 1;
        count++;
    }
    return count;
}

543. 二叉树的直径

返回任意两节点间最长路径的长度。

分析：直径不一定经过根节点。需要在遍历过程中更新全局最大直径，即左深度 + 右深度。

int maxDepth(struct TreeNode* root, int* diameter) {
    if (root == NULL) return 0;
    int left = maxDepth(root->left, diameter);
    int right = maxDepth(root->right, diameter);
    *diameter = (*diameter > left + right) ? *diameter : left + right;
    return (left > right ? left : right) + 1;
}

int diameterOfBinaryTree(struct TreeNode* root) {
    int diameter = 0;
    maxDepth(root, &diameter);
    return diameter;
}

617. 合并二叉树

将两棵树合并，重叠节点值相加。

分析：递归合并十分干脆。若某节点为空直接返回另一个节点，否则创建新节点累加值并递归合并子树。

struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2) {
    if (t1 == NULL) { return t2; }
    if (t2 == NULL) { return t1; }
    struct TreeNode* merged = malloc(sizeof(struct TreeNode));
    merged->val = t1->val + t2->val;
    merged->left = mergeTrees(t1->left, t2->left);
    merged->right = mergeTrees(t1->right, t2->right);
    return merged;
}