面试C++常考的问题：链表和数组有什么区别呢？
1、链表是链式存储结构，数组是顺序存储结构。
2、链表通过指针连接元素与元素，而数组则是把所有元素按顺序进行存储。（就是说链表在内存可以不连续，数组则是连续存储的。）
3、链表的插入和删除元素比较简单，不需要移动元素，且较为容易实现长度的扩充，但是查询元素比较困难，数组是查询比较快，但是删除和增加会比较麻烦。（数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。）
4、数组在使用前需要固定大小，如果太小，会导致数组越界；如果太大，会造成内存资源浪费；而链表则能够动态分配内存，实现用多少申请多少
5、数组元素在栈区，链表元素在堆区；
6、数组使用完后系统自动释放空间，链表使用完后需要人为通过free释放空间；
7、数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)（数组定位元素时可以根据下标直接定位，而链表则需要遍历，因此在定位元素时，数组优于链表）
所以。。。。什么是链表呢？直接上栗子！！
单向链表
单向链表中包含数据域和指针域，其中数据域用于存放数据，指针域用来连接当前结点和下一节点。
struct Node {
int value;
Node *next;
};
双向链表
双向链表中同样有数据域和指针域，不同之处在于指针域有左右（或上一个、下一个）之分，用来连接上一个节点、当前结点、下一个结点。
struct Node {
int value;
Node *left;
Node *right;
};
一个简单的应用就是反转链表:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
假设链表为 1→2→3→∅，我们想要把它改∅←1←2←3。
在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
};
[参考链接]
https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/solution/fan-zhuan-lian-biao-by-leetcode-solution-jvs5/
https://www.html.cn/qa/other/21664.html
https://blog.csdn.net/weixin_30636089/article/details/97230131
https://oi-wiki.org/ds/monotonous-stack/
