【C语言进阶】手把手教你实现“双链表求和”：从数组到链表的思维跃迁

写在前面：
很多 C 语言初学者在学完指针和结构体后，面对“链表”往往一头雾水。
“为什么有数组了还要链表？”
“malloc 到底在干什么？”
“指针指来指去晕死了！”

本文将以一道经典的“双链表求和”题目为例，不堆砌概念，而是用形象的比喻和工程化的代码，带你彻底攻克链表难关。特别针对 Visual Studio 用户，提供了独家的避坑指南。

目录

1. 题目解析：此“双”非彼“双”
2. 核心概念：像“寻宝游戏”一样的链表
3. 步步为营：手写链表构建（尾插法详解）
4. 核心逻辑：双指针同步遍历
5. 环境避坑：Visual Studio 的“坏脾气”
6. 完整源码（可直接运行）
7. 总结与思考

1. 题目解析：此“双”非彼“双”

首先，我们要澄清一个极易混淆的概念。

• 数据结构中的“双向链表” (Doubly Linked List)：每个节点有两个指针，一个指前 (prev)，一个指后 (next)。
• 本题的“双链表”：指的是 “两个” 单向链表 (Two Singly Linked Lists)。

📝 任务描述：

1. 输入：一个整数 n，和两个长度为 n 的数组 A 和 B。
2. 转换：把数组 A 变成链表 ListA，数组 B 变成链表 ListB。
3. 计算：把 ListA 里每个节点的值，加到 ListB 对应节点上。
4. 输出：打印计算后的 ListB。

示例：

数组 A: [1, 2, 3]
数组 B: [10, 20, 30]

结果： 11 22 33 (即 1+10, 2+20, 3+30)

2. 核心概念：像“寻宝游戏”一样的链表

为什么要费劲把数组转成链表？这不仅仅是做题，而是为了理解内存。

🚂 数组 (Array)：电影院的座位

数组就像电影院的一排座位。

• 特点：座位是连在一起的。
• 优势：你想找第 5 个座位，直接走过去就行（随机访问快）。
• 劣势：如果座位满了，想加个座？不行，得把整个电影院拆了重建（扩容成本高）。

🗺️ 链表 (Linked List)：寻宝游戏

链表就像一场寻宝游戏。

• 特点：线索散落在城市的各个角落（内存不连续）。
• 结构：每个线索点（节点）都有两样东西：
  1. 宝箱（val）：存放的数据。
  2. 下一站的地址（next）：指向下一个线索在哪里。
• 优势：想加个线索？随便找个空地放宝箱，把上一个线索的地址改一下指向这里就行（动态扩容快）。
• 劣势：想找第 5 个线索？必须从第 1 个开始顺藤摸瓜（查找慢）。

C 语言中的定义：

typedef struct ListNode {
    int val;                // 宝箱：存数值
    struct ListNode* next;  // 纸条：存下一个节点的地址
} ListNode;

3. 步步为营：手写链表构建（尾插法详解）

构建链表是新手的第一个噩梦。最常用的方法是尾插法，因为它能保持元素的顺序（输入 1,2,3 -> 链表 1,2,3）。

如果不使用尾指针，每插入一个元素都要从头跑到尾，效率是 $O(N^2)$。
使用尾指针 (tail)，效率提升为 $O(N)$。

🔧 算法图解

假设我们要插入数组 [10, 20]。

第一步：创建头节点（基地）
我们先用 malloc 申请第一个节点，存入 10。
此时，头指针 head 和尾指针 tail 都指向它。

      head
       |
       v
    +------+
    |  10  |  <-- tail
    +------+

第二步：插入新节点 20

1. malloc 一个新节点，存入 20。
2. 让当前 tail（也就是节点 10）的 next 指向新节点。
3. 关键点：把 tail 标签移动到新节点上。

     head
      |
      v
   +------+      +------+
   |  10  | ---> |  20  |
   +------+      +------+
                    ^
                    |
                   tail (更新到这里)

💻 代码实现片段

ListNode* createList(int* arr, int n) {
    if (n <= 0) return NULL;

    // 1. 创建头节点
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    head->val = arr[0];
    head->next = NULL;

    // 2. 初始化尾指针
    ListNode* tail = head;

    // 3. 循环创建后续节点
    for (int i = 1; i < n; i++) {
        ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
        newNode->val = arr[i];
        newNode->next = NULL;

        tail->next = newNode; // 旧尾巴指向新节点
        tail = newNode;       // 尾指针移动到新节点
    }

    return head;
}

4. 核心逻辑：双指针同步遍历

有了两个链表 ListA 和 ListB，求和逻辑就非常简单了。我们用两个指针 pA 和 pB 同时出发。

void addListToB(ListNode* listA, ListNode* listB) {
    // 只要两个链表都没走到头
    while (listA != NULL && listB != NULL) {
        // 把 A 的值加到 B 上
        listB->val += listA->val; 

        // 两个人同时往前走一步
        listA = listA->next;
        listB = listB->next;
    }
}

思考：如果两个链表长度不一样怎么办？
目前的代码会停在短链表的末尾。在实际的大数加法中，通常需要处理剩余的节点和进位（Carry）。

5. 环境避坑：Visual Studio 的“坏脾气”

很多同学在 VS 中写 C 语言会遇到报错，这里总结两个最常见的问题。

🔴 坑 1：变长数组 (VLA) 报错

错误写法：

int n;
scanf("%d", &n);
int arr[n]; // VS 报错：表达式必须含有常量值

原因：VS 的 MSVC 编译器默认遵循旧标准 (C89)，不支持用变量定义数组长度。
解决：使用 malloc 动态分配。

int* arr = (int*)malloc(n * sizeof(int));
// ... 使用完记得 free(arr)

🔴 坑 2：scanf 安全警告

报错：error C4996: 'scanf': This function or variable may be unsafe...
原因：微软觉得 scanf 容易造成缓冲区溢出，推荐用 scanf_s。但 scanf_s 是微软特有的，不跨平台。
解决：在代码文件的最第一行（必须是第一行）加上：

#define _CRT_SECURE_NO_WARNINGS

6. 完整源码（可直接运行）

复制以下代码到 Visual Studio 的 .c 文件中即可运行。

#define _CRT_SECURE_NO_WARNINGS // 1. 屏蔽安全警告

#include <stdio.h>
#include <stdlib.h>

// --- 数据结构定义 ---
typedef struct ListNode {
    int val;
    struct ListNode* next;
} ListNode;

// --- 函数声明 ---
ListNode* createList(int* arr, int n);
void addListToB(ListNode* listA, ListNode* listB);
void printList(ListNode* head);
void freeList(ListNode* head);

int main() {
    int n;
    // 读取数组长度
    if (scanf("%d", &n) != 1) return 0;

    // 2. 动态分配数组内存 (解决 VS 不支持 int arr[n] 的问题)
    int* arrA = (int*)malloc(n * sizeof(int));
    int* arrB = (int*)malloc(n * sizeof(int));

    // 内存分配检查
    if (!arrA || !arrB) {
        printf("内存分配失败！\n");
        return 1;
    }

    // 读取输入
    for (int i = 0; i < n; i++) scanf("%d", &arrA[i]);
    for (int i = 0; i < n; i++) scanf("%d", &arrB[i]);

    // 3. 核心步骤：数组 -> 链表
    ListNode* listA = createList(arrA, n);
    ListNode* listB = createList(arrB, n);

    // 4. 核心步骤：链表求和
    addListToB(listA, listB);

    // 5. 输出结果
    printList(listB);

    // 6. 善后：释放所有堆内存（养成好习惯！）
    freeList(listA);
    freeList(listB);
    free(arrA);
    free(arrB);

    return 0;
}

// --- 函数实现 ---

// 使用【尾插法】构建链表
ListNode* createList(int* arr, int n) {
    if (n <= 0) return NULL;

    // 创建头节点
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    if (!head) exit(1);
    head->val = arr[0];
    head->next = NULL;

    // 尾指针：始终指向链表最后一个节点
    ListNode* tail = head;

    for (int i = 1; i < n; i++) {
        ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
        if (!newNode) exit(1);
        newNode->val = arr[i];
        newNode->next = NULL;

        // 关键操作：挂接 + 移动
        tail->next = newNode;
        tail = newNode;
    }
    return head;
}

// 链表相加逻辑
void addListToB(ListNode* listA, ListNode* listB) {
    while (listA != NULL && listB != NULL) {
        listB->val += listA->val;
        listA = listA->next;
        listB = listB->next;
    }
}

// 打印链表
void printList(ListNode* head) {
    ListNode* cur = head;
    while (cur != NULL) {
        printf("%d", cur->val);
        if (cur->next != NULL) printf(" ");
        cur = cur->next;
    }
    printf("\n");
}

// 释放链表内存
void freeList(ListNode* head) {
    ListNode* cur = head;
    while (cur != NULL) {
        ListNode* temp = cur; // 先暂存
        cur = cur->next;      // 后移
        free(temp);           // 再释放
    }
}

7. 总结与思考

恭喜你！通过这道题，你已经掌握了 C 语言链表开发的 80% 核心套路：

1. 定义结构体：val + next。
2. 创建链表：malloc + 尾插法（tail 指针）。
3. 遍历链表：while(cur != NULL) { cur = cur->next; }。
4. 内存管理：有 malloc 必有 free。

🚀 进阶挑战：
如果题目改成“大数相加”（例如两个 100 位的整数相加），普通的 int 肯定存不下。
这时候，链表的优势就体现出来了：每个节点存一位数字，模拟竖式加法，处理进位。
这才是链表在工程中真正的威力所在！

希望这篇博客能帮你打通 C 语言链表的任督二脉！如果有疑问，欢迎在评论区留言讨论。👇