C++ 算法实战：字符串处理与链表相交问题解析

删除公共字符

题目要求从第一个字符串中移除第二个字符串包含的所有字符。输入可能包含空格，需要特别注意读取方式。

核心思路

直接在原字符串上删除字符开销较大，每次删除都涉及内存移动。更优的做法是构建一个新的结果字符串，或者利用哈希表标记待删除的字符。

我们可以先遍历第二个字符串 str2，将其出现的字符标记出来。接着遍历 str1，只保留那些未被标记的字符。这里使用一个布尔数组作为哈希表即可，因为 ASCII 码范围有限，空间占用极小。

代码实现

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s, t;
    // 使用 getline 读取可能包含空格的行
    getline(cin, s);
    getline(cin, t);

    bool hash[200] = {false};
    // 标记 str2 中出现的所有字符
    for (auto& e : t) {
        hash[e] = true;
    }

    string ret;
    // 构建新字符串，跳过被标记的字符
    for (auto& e : s) {
        if (!hash[e]) {
            ret += e;
        }
    }
    cout << ret << endl;
    return 0;
}

两个链表的第一个公共结点

给定两个单链表，找出它们相交的第一个节点。如果不存在交点，返回 nullptr。

核心思路

这道题经典的解法是利用双指针技巧。假设两个链表分别为 A 和 B，A 的长度为 lenA，B 的长度为 lenB。

如果直接比较，需要知道长度差。另一种更优雅的思路是让两个指针同时开始遍历。当指针 cur1 走到 A 的末尾时，让它跳转到 B 的头节点继续走；同理，cur2 走到 B 的末尾后跳转到 A 的头节点。

这样，两个指针走过的总路程都是 lenA + lenB。如果存在交点，它们会在交点处相遇；如果不存在交点，它们最终都会到达 nullptr 并相遇。这个过程中不需要预先计算链表长度。

代码实现

  {
:
    {
        ListNode* cur1 = pHead1;
        ListNode* cur2 = pHead2;
        
         (cur1 != cur2) {
            
            cur1 = (cur1 == ) ? pHead2 : cur1->next;
            cur2 = (cur2 == ) ? pHead1 : cur2->next;
        }
         cur1;
    }
};