链表相关问题整理

1、比较顺序表和链表的优缺点， 说说它们分别再什么场景下使用？

顺序表存储（典型的数组）

• 原理：顺序表存储是将数据元素放到一块连续的内存存储空间，相邻数据元素的存放地址也相邻（逻辑与物理统一）。

链表存储

• 原理：链表存储是在程序运行过程中动态的分配空间，只要存储器还有空间，就不会发生存储溢出问题，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点关系间的指针。

优缺点比较：

• 1、顺序表支持随机访问，单链表不支持随机访问；
• 2、顺序表的插入/删除效率低，时间复杂度为O(N)（除尾插尾删），单链表的插入/删除效率高，时间复杂度为O(1)；
• 3、顺序表的CPU高效缓存效率更高，单链表的CPU高效缓存效率低。

2、从尾到头打印单链表(逆序)

如何将链表逆序，取决于题目的要求。如果面试官只要求打印，一般不改动链表结构为好，如果要求改变链表的方向，则需要改变结构，再顺序打印。

• 方法1：只逆序打印，不改变结构。采用递归，到达尾结点时打印输出，否则进入下一个结点的递归，当递归一层层退出的时候，便可以实现从尾到头的打印。
• 方法2：头插法，改变结构。从第二个结点开始往后，依次把每个结点移至链表头部，要注意最后链表不要是断裂的。
• 方法3：改变指针方向。从头结点开始，依次把结点的next指针断开指向该结点的前结点。要注意保存好，前结点、当前结点和下一个结点。
• 方法4：只逆序打印，不改变结构。利用栈的后进先出来实现逆序。

image.png