提前声明：本文所有代码均按照简易，理解思路开始写，请勿参考Linus的 易读理解性 代码标准。

合并链表

本章节所学习知识如下：

指针
结构体
链表的构造
链表的遍历
链表的插入
链表的删除
链表的合并
链表的反转
链表的复制
链表的排序
链表的搜索
链表的删除重复元素
虚拟头结点构造

学习

学习指针

在本章节中，我们只学习基本的指针概要。

指针

指针是一个变量，它指向一个地址。指针变量可以指向任意数据类型，但是它只能指向一个地址。所以实际上指针是一个16进制数，它表示的是一个地址。

Demo1

int i = 10;

int *p = &i;

在如上图所示代码中，p是一个指针变量，它指向一个整数变量i的地址。

& 是取地址运算符，它用于获取变量的地址。

在这里，int *p = &i;表示将变量i的地址赋给指针变量p。

所以，易得：

Demo2

int j = *p;

在上面这行代码中，我们让变量j的值等于变量i的值，通过地址运算。

这里的 *p 表示变量p的值，即变量p的地址。

综上所述，易得：

指针指向一个地址，就像城市邮编和城市地址对应一样。
赋值给指针时，我们要使用取地址符号，即通过城市地址获得城市邮编，即C中的&。
取值时，要使用指针变量的值，即通过城市邮编获得城市地址，即C中的*。

结构体

结构体是一个数据类型，它由一个或多个变量组成，这些变量可以是基本数据类型，也可以是结构体。

Demo3

struct student {
};

在上面的代码中，我们定义了一个结构体student。没错，就是如此简单。这就是最简单的结构体的定义，其中 student 是由你自行命名的一串符合规定的类似变量名。

Demo4

接下来，我们为这个结构体添加属性。

struct student {
  int age;
  bool attend;
};

在上面的代码中，我们为 student 结构体添加了两个属性，即age和attend。

其中:

int age 表示 age 属性是一个整数
bool attend 表示 attend 属性是一个布尔值。

这就是结构体中如何添加属性，我们只需要按照行定义变量即可。此时，我们可以将结构体作为一个类型使用，就像是int, bool, char, double, ...一样。

Demo5

struct student {
  int age;
  bool attend;
};

int main() {
  student tag;

  tag.age = 18;
  tag.attend = true;

  return 0;
}

在上面的代码中，我们定义了一个结构体，然后创建了一个结构体变量（学生）tag，并初始化了它的属性。

设置他的年龄为18，参与了算法学习！

这就是，你需要知道的所有前缀知识（基本知识不做考虑）。

链表

在学习链表之前，我们应该了解数组。

数组是一种数据结构，它是一个连续的内存空间，其中元素之间通过索引进行访问。其中索引即表示偏移量（offset）。

而链表则不同

链表是一种数据结构，它是一个不连续的内存空间，其中元素之间通过指针进行访问。其中指针即表示偏移量（offset）。

总之，你只需要知道数组是连续堆在一起的，所以我知道数组长度和第一个，我就可以访问到所有。而链表你只需要知道第一个，他会告诉你下一个在哪里，如果没有下一个，他就会告诉你结束了（NULL）。

链表的构造

要构造一个链表，我们应该思考如何去表示这种指向性的数据结构。

考虑以下结构

链表结构#1

让每一个结点指向下一个结点，同时每个结点还有属于自己的名字（在这里使用int代替，可以理解为学号）（标蓝色表示结点是第一个，即头结点）

struct LinkedList {
  int value;
  LinkedList *next;
};

在上述代码中，我们定义了一个链表结构，其中包含两个属性，即value和next。

value 表示结点的值
next 表示下一个结点的地址

在这里，解释一下 *next

LinkedList *next 表示定义了一个指向下一个类型为LinkedList地址的指针。

在这里，我们可以理解将不同的类型看为直辖市，一线城市，二线城市。

所以，这个指向直辖市邮编的指针强调下一个类型必须是直辖市（也可以是NULL 即没有）

链表的遍历

综上所述，我们要遍历链表，其实只需要拿到头结点然后不断地去找next这个地方有没有东西。

提一嘴，在指针中，访问属性时，需要使用->，而不是.。

LinkedList *head = new LinkedList;

while (head != NULL) {
  LinkedList *temp = head->next;

  // 此时的 temp 即为当前获得的地址

  // 进行下一次查找
  head = temp;
}

链表的插入

在链表插入分为 2 种情况，在指定位置插入和尾部插入，在这里我们只讨论尾部插入情况，指定位置插入可以自行举一反三（index）。

LinkedList *head = new LinkedList;

while (head->next != NULL) {
  LinkedList *temp = head->next;
  head = temp;
}

在这里不同的是，我们要找到一个结点，他的next是NULL，也就是最后一个结点。因为他的下一个结点指向NULL了，表示他之后没有了，所以我们找到这个结点，让他的next指向要插入的结点。

head = insert;

其余链表用法可自行搜索！

题目

接下来，我们来做题。

题目描述

已有a、b两个链表，每个链表中的结点包括学号、成绩。要求把两个链表合并，按学号升序排列。

输入

第一行，a、b两个链表元素的数量N、M,用空格隔开。接下来N行是a的数据然后M行是b的数据每行数据由学号和成绩两部分组成

输出

按照学号升序排列的数据

即此图

根据此题描述，易得2个知识点：

链表
排序

要求按照学号升序，所以我们应当先排序再插入。

刚开始没有太多思路，考虑先搭建模板框架。考虑将结构体表示出来看看是否有思路。

最终解法采用 C++ 。（C中同理）

#include <bits/stdc++.h>

using namespace std;

struct Node
{
  int score;
  int id;

  Node *next;
};

int main()
{

  return 0;
}

此时，易知我们需要考虑输入数据，即建立链表。考虑在建立链表的时候就排序结束。

我们先建立一个函数，给他一个头结点，让他自动帮我们插入。就像是续命一样。

void insert(Node *head, Node *insert)
{
  Node *temp = head;
  while (temp->next != NULL)
  {
    // 这里什么都不用做
  }

  // 此时已经找到最后一个
  temp->next = insert;
}

通过这里，我们就马上能反应过来，这样在最后插入就没有排序作用了。所以我们易得其实是让我们在指定位置去插入这个node，关键点变成如何去找到这个位置。

找到位置也很简单，我们定义一个变量i去定义，因为我们在刚开始建立的时候就采用从小到大去排序，所以我们一定知道下一个的节点的学号一定大于等于当前节点的学号。

因此，我们只需要找到下一个节点的学号大于等于当前插入节点的学号，那么就是当前节点的位置。

我们在原来的函数上进行稍加改造，让他不再在最后插入。

void insert(Node *head, Node *insert)
{
  Node *temp = head;

  // 和当前的比较，只要当前的的学号大于等于当前插入的学号，那么就找到位置了
  while ( temp->next != NULL && temp->next->id < insert->id)
  {
    temp = temp->next;
  }

  // 此时已经找到目标
  // 插入后粘上
  insert->next = temp->next;
  temp->next = insert;
}

最后，我们再完善一下main函数，题目就做完了。这里要额外提醒一下，因为题目描述是合并链表，也就是说无论如何最后只有一个链表。所以我们读入的时候就把他们合并起来读入，一边读入一边排序，这样读完了自动就排序好。最后再简单遍历一下，结果就出来了！

完整代码如下：

#include <bits/stdc++.h>

using namespace std;

struct Node
{
  int score;
  int id;

  Node *next;
};

void insert(Node *head, Node *insert)
{
  Node *temp = head;
  while (temp->next != NULL && temp->next->id < insert->id)
  {
    temp = temp->next;
  }

  insert->next = temp->next;
  temp->next = insert;
}

int main()
{
  // 读入N和M 分别表示a和b的数据
  int N, M;
  scanf("%d %d", &N, &M);

  // 先定义一个头结点，这样整个链表我们就都可以访问了
  Node *head = new Node;
  head->next = NULL;

  int i;
  for (i = 0; i < N + M; ++i)
  {
    Node *a = new Node;

    scanf("%d %d", &a->id, &a->score);

    // 初始化
    a->next = NULL;

    insert(head, a);
  }

  // 读入即合并结束，打印即可
  Node *cur = head->next;
  while (cur != NULL)
  {
    printf("%d %d\n", cur->id, cur->score);

    cur = cur->next;
  }

  return 0;
}

（在这里我们使用虚拟头结点，其实就是先声明一个结点不用）

现在，你是否有信心挑战题目？以下是我推荐的一些你可以拿来练手的其他题目：

合并两个有序链表（考虑双指针、连线）移除链表元素反转链表两两交换倒数链表删除链表相交环形链表II 设计链表（难度较大，建议学习OOP知识后做）

你可以在拓展题目中学习虚拟头结点技巧、增删改查（CRUD）、双指针遍历法、环形入口判断。

因为本章主要做初学者了解使用，所以许多概念不提出衍生，有需要者可以自行搜索。部分概念也进行模糊化讲解，不做细分要求，有需要者可以自行搜索。

最后，你可以点击右上角的 Sponsor 按钮来赞助我！

合并链表

学习

Source files