关于设置关注可见

设置这个就是为了卡一下网上的各种搬运，可以关注之后再取关，这样就可以看了hh

0.序

如果在这一块遇见啥问题可以留言讨论

while(keep) ability++;

1. 前言

链表估计是笔试面试常出现的东西了，竞赛里倒是不常会出现(可能是因为和其他东西比起来太简单了）=。=。。

2. 啥是链表

肥肠的明显，链表的存储不是连续的，存储密度小于1
对于一个链表节点，我们有数据域和指针域两个部分
数据域是用来存储数据的，指针域用来存储下一个链表节点

struct Node {int val;Node *next;};

3. 关于实现

struct ListNode {int val;ListNode *next;}ListNode *head;void init() {    head = new ListNode();    head -> next = nullptr;}void insert(ListNode *p, int val) {    ListNode *q = new ListNode();    q -> val = val;    q -> next = p -> next;    p -> next = q;}

举个栗子

力扣21.合并两个有序链表

怎么做嘞？非常的简单，使用两个游标(指针)从头遍历两个链表，另外再开辟一个新的表头节点$head$和一个新的游标$l3$，用来存放答案和往链表中添加元素。

在遍历的时候进行判断：
如果$l1$的当前元素更小，就让$l3$指向$l1$，这样就把$l1$添加到了答案中。
对$l2$同理。
如果其中一个链表已经被遍历完了，那就可以把另一个链表直接添加到答案中了(因为链表都是有序的)

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode() : val(0), next(nullptr) {} *     ListNode(int x) : val(x), next(nullptr) {} *     ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */class Solution {public:    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode *l3, *head; head = (ListNode *)malloc(sizeof(ListNode));//C语言的内容，比new要快 l3 = head; while (l1 != nullptr && l2 != nullptr) {     if (l1 -> val < l2 -> val) {  l3 -> next = l1;  l1 = l1 -> next;     }     else {  l3 -> next = l2;  l2 = l2 -> next;     }     l3 = l3 -> next; } l3 -> next = (l1 != nullptr ? l1 : l2); return head -> next;    }};

读完代码后会发现，诶？为啥返回的是head -> next而不是head嘞？

关于虚拟头结点

可能第一次会写出这样的一段

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode *l3, *head;  if (l1 -> val < l2 -> val) {     head = l1;     l1 = l1 -> next; } else {     head = l2;     l2 = l2 -> next; } l3 = head; while (l1 != nullptr && l2 != nullptr) {     if (l1 -> val < l2 -> val) {  l3 -> next = l1;  l1 = l1 -> next;     }     else {  l3 -> next = l2;  l2 = l2 -> next;     }     l3 = l3 -> next; } l3 -> next = (l1 != nullptr ? l1 : l2); return head;    }

这样就是head直接指向链表的第一个元素。写完一运行样例，淦 第二个就过不去了，然后加上一通判断，最后也是能过了

啊 但是——
如果我们引入虚拟头结点，就不需要考虑头结点的特判了

为啥叫虚拟头结点

我们在链表的头结点之前，再添加一个我们定义的头结点，这个头结点并不存储数据，只存储一个指针，指向真正的链表头结点，这样一来就可以往虚拟头结点的后面直接添加元素了，就不需要再对head进行特判(一通胡扯)
所以就变成了现在的样子

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode *l3, *head; head = (ListNode *)malloc(sizeof(ListNode)); l3 = head; while (l1 != nullptr && l2 != nullptr) {     if (l1 -> val < l2 -> val) {  l3 -> next = l1;  l1 = l1 -> next;     }     else {  l3 -> next = l2;  l2 = l2 -> next;     }     l3 = l3 -> next; } l3 -> next = (l1 != nullptr ? l1 : l2); return head -> next;    }