单链表应用：经典算法题与通讯录实现

1.3 合并两个有序链表

题目描述：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解题思路： 创建一个新的链表，通过两个指针遍历两个链表，并进行比较大小，把小的节点接到新链表后面。

代码实现：

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    ListNode* l1 = list1;
    ListNode* l2 = list2;
    ListNode* newhead = NULL;
    ListNode* newtail = NULL;
    // 处理空链表情况
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;
    // 确定第一个节点（初始化 newhead 和 newtail）
    if (l1->val < l2->val) {
        newhead = newtail = l1;
        l1 = l1->next;
    } else {
        newhead = newtail = l2;
        l2 = l2->next;
    }
    while (l1 && l2) {
        if (l1->val < l2->val) {
            newtail->next = l1; // 将 l1 节点挂到尾部
            l1 = l1->next; // l1 后移
        } else {
            newtail->next = l2; // 将 l2 节点挂到尾部
            l2 = l2->next; // l2 后移
        }
        newtail = newtail->next; // newtail 移动到新节点
    }
    if (l1) newtail->next = l1;
    if (l2) newtail->next = l2;
    return newhead;
}

1.4 链表的中间节点

题目描述：给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

解题思路：

• 使用快慢指针：快指针一次走两步，慢指针一次走一步
• 当快指针到达末尾时，慢指针恰好指向中间节点

代码实现：

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    /*int count=0;
    if(head==NULL) return head;
    ListNode* pcur=head;
    while(pcur) {
        pcur=pcur->next;
        count++;
    }
    pcur=head;
    for(int i=0;i<count/2;i++) {
        pcur=pcur->next;
    }
    return pcur; */
    ListNode* slow,*fast;
    slow=fast=head;
    while(fast&&fast->next) {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}

1.5 环形链表的约瑟夫问题

问题描述：编号为 1 到 n 的 n 个人围成一圈。从第 1 个人开始报数，数到 m 的人出列，然后从下一个人继续报数，直到所有人都出列。请输出出列顺序。

背景：这是著名的约瑟夫斯问题（Josephus problem）。

解题思路：

• 可以用循环链表模拟这个过程
• 每次数到 m 的人移除，从下一个人继续
• 直到链表为空

代码实现：

typedef struct ListNode ListNode;
ListNode* buynode(int num) {
    ListNode* node=(ListNode*)malloc(sizeof(ListNode));
    if(node==NULL) {
        exit(1);
    }
    node->val=num;
    node->next=NULL;
    return node;
}
ListNode* CreatecirList(int n) {
    ListNode* head=buynode(1);
    ListNode* ptail=head;
    for(int i=2;i<=n;i++) {
        ptail->next=buynode(i);
        ptail=ptail->next;
    }
    ptail->next=head;
    return ptail;
}
int ysf(int n, int m) {
    ListNode* prev=CreatecirList(n);
    ListNode* pcur=prev->next;
    int count=1;
    while(pcur->next!=pcur) {
        if(count==m) {
            prev->next=pcur->next;
            free(pcur);
            pcur=prev->next;
            count=1;
        } else {
            pcur=pcur->next;
            prev=prev->next;
            count++;
        }
    }
    return pcur->val;
}

1.6 分割链表

题目描述：给你一个链表的头节点 head 和一个特定值 x，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。

解题思路：

• 创建两个虚拟头节点，分别存放小于 x 和大于等于 x 的节点
• 遍历原链表，将节点按条件接入两个新链表
• 最后将两个链表连接起来

代码实现：

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x) {
    if(head==NULL) {
        return NULL;
    }
    ListNode* lesshead,* lesstail;
    ListNode* greathead,* greattail;
    lesshead=lesstail=(ListNode*)malloc(sizeof(ListNode));
    greathead=greattail=(ListNode*)malloc(sizeof(ListNode));
    ListNode* pcur=head;
    while(pcur) {
        if((pcur->val)<x) {
            lesstail->next=pcur;
            lesstail=lesstail->next;
        } else {
            greattail->next=pcur;
            greattail=greattail->next;
        }
        pcur=pcur->next;
    }
    greattail->next=NULL;
    lesstail->next=greathead->next;
    ListNode* ret=lesshead->next;
    free(lesshead);
    free(greathead);
    return ret;
}

第二部分：基于单链表再实现通讯录

在上一篇文章中，我们用顺序表实现了通讯录。现在，我们用单链表重新实现，并对比两者的差异。

2.1 设计思路

• 链表节点中的数据域存储联系人信息（结构体 PeoInfo）
• 链表提供动态添加、删除、查找、修改等功能
• 数据持久化：程序启动时从文件加载，退出时保存

2.2 代码结构

SList.h（链表定义及接口）

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "contact.h"
typedef struct PersonInfo SLTDataType; // 联系人类型
typedef struct SListNode {
    SLTDataType data;
    struct SListNode* next;
} SLTNode; // 基本操作声明
void SLTPrint(SLTNode* phead);
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void SLTErase(SLTNode** pphead, SLTNode* pos);
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
void SLTEraseAfter(SLTNode* pos);
void SLTDestroy(SLTNode** pphead);

contact.h（联系人信息及通讯录接口）

#pragma once
#include <stdio.h>
#include <string.h>
#define NAME_MAX 100
#define SEX_MAX 4
#define TEL_MAX 12
#define ADDR_MAX 100
// 联系人信息结构
typedef struct PersonInfo {
    char name[NAME_MAX];
    char sex[SEX_MAX];
    int age;
    char tel[TEL_MAX];
    char addr[ADDR_MAX];
} PeoInfo;
// 前置声明链表类型（避免循环包含）
typedef struct SListNode contact; // 通讯录功能接口
void InitContact(contact** con); // 初始化
void AddContact(contact** con); // 添加联系人
void DelContact(contact** con); // 删除联系人
void ShowContact(contact* con); // 显示所有
void FindContact(contact* con); // 查找联系人
void ModifyContact(contact** con); // 修改联系人
void DestroyContact(contact** con); // 销毁通讯录

contact.c（通讯录功能实现）

#define _CRT_SECURE_NO_WARNINGS
#include "contact.h"
#include "SList.h"
// 从文件加载数据
static void LoadContact(contact** con) {
    FILE* pf = fopen("contact.dat", "rb");
    if (pf == NULL) {
        // 文件不存在，正常情况
        return;
    }
    PeoInfo info;
    while (fread(&info, sizeof(PeoInfo), 1, pf)) {
        SLTPushBack(con, info); // 插入链表尾部
    }
    fclose(pf);
    printf("历史数据加载成功！\n");
}
// 保存数据到文件
static void SaveContact(contact* con) {
    FILE* pf = fopen("contact.dat", "wb");
    if (pf == NULL) {
        perror("保存文件失败");
        return;
    }
    contact* cur = con;
    while (cur) {
        fwrite(&(cur->data), sizeof(PeoInfo), 1, pf);
        cur = cur->next;
    }
    fclose(pf);
    printf("数据保存成功！\n");
}
// 初始化通讯录
void InitContact(contact** con) {
    *con = NULL; // 初始为空链表
    LoadContact(con);
}
// 按姓名查找节点（返回节点指针）
static contact* FindByName(contact* con, const char* name) {
    contact* cur = con;
    while (cur) {
        if (strcmp(cur->data.name, name) == 0) {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}
// 添加联系人
void AddContact(contact** con) {
    PeoInfo info;
    printf("请输入姓名：");
    scanf("%s", info.name);
    printf("请输入性别：");
    scanf("%s", info.sex);
    printf("请输入年龄：");
    scanf("%d", &info.age);
    printf("请输入电话：");
    scanf("%s", info.tel);
    printf("请输入地址：");
    scanf("%s", info.addr);
    SLTPushBack(con, info);
    printf("添加成功！\n");
}
// 删除联系人
void DelContact(contact** con) {
    char name[NAME_MAX];
    printf("请输入要删除的联系人姓名：");
    scanf("%s", name);
    contact* pos = FindByName(*con, name);
    if (pos == NULL) {
        printf("未找到该联系人！\n");
        return;
    }
    SLTErase(con, pos);
    printf("删除成功！\n");
}
// 显示所有联系人
void ShowContact(contact* con) {
    if (con == NULL) {
        printf("通讯录为空！\n");
        return;
    }
    printf("\n%-10s %-4s %-4s %-15s %-20s\n", "姓名", "性别", "年龄", "电话", "地址");
    printf("------------------------------------------------\n");
    contact* cur = con;
    while (cur) {
        printf("%-10s %-4s %-4d %-15s %-20s\n", cur->data.name, cur->data.sex, cur->data.age, cur->data.tel, cur->data.addr);
        cur = cur->next;
    }
}
// 查找联系人
void FindContact(contact* con) {
    char name[NAME_MAX];
    printf("请输入要查找的联系人姓名：");
    scanf("%s", name);
    contact* pos = FindByName(con, name);
    if (pos == NULL) {
        printf("未找到该联系人！\n");
        return;
    }
    printf("\n姓名：%s\n性别：%s\n年龄：%d\n电话：%s\n地址：%s\n", pos->data.name, pos->data.sex, pos->data.age, pos->data.tel, pos->data.addr);
}
// 修改联系人
void ModifyContact(contact** con) {
    char name[NAME_MAX];
    printf("请输入要修改的联系人姓名：");
    scanf("%s", name);
    contact* pos = FindByName(*con, name);
    if (pos == NULL) {
        printf("未找到该联系人！\n");
        return;
    }
    printf("请输入新的姓名：");
    scanf("%s", pos->data.name);
    printf("请输入新的性别：");
    scanf("%s", pos->data.sex);
    printf("请输入新的年龄：");
    scanf("%d", &pos->data.age);
    printf("请输入新的电话：");
    scanf("%s", pos->data.tel);
    printf("请输入新的地址：");
    scanf("%s", pos->data.addr);
    printf("修改成功！\n");
}
// 销毁通讯录（保存数据并释放内存）
void DestroyContact(contact** con) {
    SaveContact(*con);
    SLTDestroy(con);
}

test.c（主程序）

#include "SList.h"
#include "contact.h"
void menu() {
    printf("\n========== 通讯录管理系统（链表版） ==========\n");
    printf("1. 添加联系人\n");
    printf("2. 删除联系人\n");
    printf("3. 查找联系人\n");
    printf("4. 修改联系人\n");
    printf("5. 显示所有联系人\n");
    printf("0. 退出系统\n");
    printf("==============================================\n");
    printf("请选择：");
}
int main() {
    contact* con = NULL;
    InitContact(&con);
    int choice;
    do {
        menu();
        scanf("%d", &choice);
        switch (choice) {
        case 1: AddContact(&con); break;
        case 2: DelContact(&con); break;
        case 3: FindContact(con); break;
        case 4: ModifyContact(&con); break;
        case 5: ShowContact(con); break;
        case 0: break;
        default: printf("无效选择！\n"); break;
        }
    } while (choice != 0);
    DestroyContact(&con);
    return 0;
}

2.3 顺序表版与链表版通讯录对比

从对比可以看出，链表在插入删除操作上更灵活，但牺牲了随机访问的能力。在实际应用中，应根据需求选择合适的数据结构。

总结

通过解决经典链表算法题和实现通讯录项目，我们深入体会了单链表的实际应用：

• 算法题训练让我们掌握了链表操作的常用技巧（双指针、哨兵节点、节点删除等）
• 通讯录项目展示了如何用链表组织动态数据，并与顺序表进行对比

链表作为基础数据结构，其指针操作的思维方式为后续学习树、图等复杂结构奠定了基础。