C语言链表比较：查找含共同电话号码的重复节点方法

首先需要明确每个节点num数组中无效位的判定规则，原结构体没有存储实际使用的号码数量，可二选一：

• 未修改结构体的通用方案：约定num数组未使用的指针赋值为NULL，遍历到NULL即判定为该节点有效号码遍历结束
• 更严谨的可扩展方案：给结构体新增int valid_num_count字段，直接存储该节点有效号码的数量，省去遍历判断NULL的额外开销

电话号码是字符串，绝对不能直接比对指针地址，必须用strcmp()比较字符串内容，否则相同号码存储在不同内存地址时会被误判为不同。

辅助函数实现：判断两个节点是否存在共同号码 #

函数逻辑为：遍历第一个节点的所有有效号码，每取出一个号码就遍历第二个节点的所有有效号码，若存在任意一组strcmp结果为0，即判定为存在共同号码。
示例代码（未修改结构体、以NULL标记无效位的版本）：

#include <string.h>
// 返回值：1 = 存在共同号码，0 = 无共同号码
int has_common_phone(node *a, node *b) {
    // 遍历a的所有有效号码
    for (int i = 0; i < 10; i++) {
        // 遇到NULL则a的有效号码遍历结束
        if (a->num[i] == NULL) break;
        
        // 遍历b的所有有效号码，查找和a->num[i]相同的项
        for (int j = 0; j < 10; j++) {
            if (b->num[j] == NULL) break;
            if (strcmp(a->num[i], b->num[j]) == 0) {
                return 1; // 找到共同号码，直接返回
            }
        }
    }
    return 0;
}

如果选择新增valid_num_count字段的方案，结构体和对应辅助函数可简化为：

// 新增valid_num_count字段的结构体定义
typedef struct node
{
    char *name;
    char *num[10];
    int valid_num_count; // 存储该节点实际使用的号码数量
    struct node* next;
} node;

// 对应简化后的辅助函数
int has_common_phone(node *a, node *b) {
    for (int i = 0; i < a->valid_num_count; i++) {
        for (int j = 0; j < b->valid_num_count; j++) {
            if (strcmp(a->num[i], b->num[j]) == 0) return 1;
        }
    }
    return 0;
}

基于上述辅助函数，通过双指针遍历链表比对所有节点对，避免重复比对已处理过的组合：

• 外层指针curr从链表头开始，逐个遍历节点
• 内层指针runner从curr->next开始向后遍历，仅和未与curr比对过的后续节点做判断
• 若比对结果为存在共同号码，直接打印两个节点的信息
  示例代码：

void print_duplicate_nodes(node *head) {
    node *curr = head;
    while (curr != NULL) {
        node *runner = curr->next;
        while (runner != NULL) {
            if (has_common_phone(curr, runner)) {
                printf("存在共享号码的节点对：[%s] 和 [%s]\n", curr->name, runner->name);
                // 若需要打印具体共享的号码，可修改has_common_phone增加传出参数，返回匹配的具体号码值
            }
            runner = runner->next;
        }
        curr = curr->next;
    }
}

如果链表长度较大，两两比对的时间复杂度为O(n²)（n为节点数），可通过哈希表优化到O(n)复杂度：

1. 初始化哈希表，键为电话号码字符串，值为关联的节点指针数组
2. 遍历链表每个节点，取出所有有效号码，把当前节点指针追加到哈希表对应号码的键值下
3. 遍历哈希表的所有键，若对应节点数组长度≥2，即说明这些节点共享该电话号码，直接打印即可

内容的提问来源于stack exchange，提问作者Sajjad Abbas