如何向多链表添加节点？按姓名排序实现及与单链表的差异

首先得明确你的多链表设计：每个节点同时属于两条独立的有序链表——一条按**名字（first name）的字母顺序串联，另一条按姓氏（last name）**的字母顺序串联。这和单链表的核心差异很明显：单链表只需要维护一条链的顺序，而你得同时把新节点插入到两条链的正确位置上。

核心思路：两次独立的有序插入 #

不管是单链表还是多链表，有序插入的核心都是找到插入位置的前驱节点，然后调整指针。区别只是多链表要做两次这个操作：一次针对nextFirst链（按名字排序），一次针对nextLast链（按姓氏排序）。

具体实现代码 #

先补全你没写完的多链表头部结构体（合理的设计应该是这样）：

typedef struct node {
    char *first;
    char *last;
    long number;
    struct node *nextFirst;  // 按first name排序的链表指针
    struct node *nextLast;   // 按last name排序的链表指针
} Node;

typedef struct mlist {
    Node *headFirst;  // 按first name排序的链表头
    Node *headLast;   // 按last name排序的链表头
} MList;

接下来是完整的插入函数实现（假设你已经掌握了节点内存分配的基础逻辑）：

#include <stdlib.h>
#include <string.h>

// 创建新节点（包含字符串内存分配）
Node* create_node(const char* first, const char* last, long number) {
    Node* new_node = malloc(sizeof(Node));
    if (!new_node) return NULL;
    
    // 为名字和姓氏分配独立内存，避免浅拷贝导致的野指针问题
    new_node->first = strdup(first);
    new_node->last = strdup(last);
    new_node->number = number;
    new_node->nextFirst = NULL;
    new_node->nextLast = NULL;
    
    return new_node;
}

// 向多链表中插入节点，同时维护两条链的字母顺序
int insert_into_mlist(MList* list, const char* first, const char* last, long number) {
    if (!list) return -1;  // 传入的链表指针为空，直接返回错误
    
    Node* new_node = create_node(first, last, number);
    if (!new_node) return -1;  // 内存分配失败
    
    // --- 第一步：插入到按first name排序的链 ---
    Node** curr_first = &list->headFirst;
    // 找到第一个名字大于新节点的位置的前驱
    while (*curr_first != NULL && strcmp((*curr_first)->first, first) < 0) {
        curr_first = &(*curr_first)->nextFirst;
    }
    // 调整指针完成插入
    new_node->nextFirst = *curr_first;
    *curr_first = new_node;
    
    // --- 第二步：插入到按last name排序的链 ---
    Node** curr_last = &list->headLast;
    // 找到第一个姓氏大于新节点的位置的前驱
    while (*curr_last != NULL && strcmp((*curr_last)->last, last) < 0) {
        curr_last = &(*curr_last)->nextLast;
    }
    // 调整指针完成插入
    new_node->nextLast = *curr_last;
    *curr_last = new_node;
    
    return 0;  // 插入成功
}

和单链表的差异对比 #

• 操作数量：单链表只需要做一次有序插入（找一个位置，调一组指针）；多链表要做两次独立的插入操作，分别维护两条链的顺序。
• 指针维护：单链表每个节点只有一个next指针；多链表每个节点有多个next指针（这里是两个），插入时要分别更新对应链的指针。
• 时间复杂度：单链表有序插入是O(n)，多链表是O(n + m)（n是名字链长度，m是姓氏链长度），本质是两次单链表插入的叠加。
• 功能优势：单链表只能按一种顺序遍历/查找；多链表支持多维度的有序操作——比如你可以快速按名字查找，也可以快速按姓氏查找，这也是多链表的设计初衷。

关键注意事项 #

1. 字符串比较：用strcmp来判断字母顺序，它会根据ASCII值比较，区分大小写。如果需要不区分大小写的排序，可以用strcasecmp（注意部分平台需要额外引入头文件或宏定义）。
2. 内存安全：创建节点时一定要给first和last分配独立内存（比如用strdup），不能直接指向传入的临时字符串，否则会出现野指针问题。
3. 重复节点处理：上面的代码会把新节点插入到同名字/姓氏节点的前面（因为strcmp返回0时循环停止）。如果想插在后面，把判断条件改成strcmp(...) <= 0；如果要避免重复插入，需要在插入前先遍历检查是否存在相同节点。
4. 空链表兼容：代码中用了指向指针的指针（Node**），可以自然处理空链表的情况，不需要额外写分支判断，代码更简洁健壮。

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