链表简介

链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和一个指向下一个节点的指针。链表可以是单向的（每个节点指向下一个节点）或者双向的（每个节点同时指向上一个节点和下一个节点）。链表通常用于实现其他数据结构，如栈、队列等，也可以作为一种独立的数据结构使用。

链表相对于数组具有一些优势和劣势：

优势：

1. 插入和删除操作效率高：链表的插入和删除操作时间复杂度为 O(1)，因为只需修改节点的指针，而不需要移动其他元素。
2. 空间利用灵活：链表的空间大小可以动态调整，不像数组需要预先分配空间大小。

劣势：

1. 随机访问效率低：链表中要访问某个元素需要从头开始逐个遍历，时间复杂度为 O(n)，而数组可以通过索引直接访问元素，时间复杂度为 O(1)。
2. 需要额外的指针空间：每个节点需要存储指向下一个节点的指针，因此链表需要额外的空间存储指针信息。

常见考察方向

在面试中，链表通常是基础题。因为它涵盖了很多基本的数据结构和算法概念，例如链表的创建、插入、删除、反转、环检测等，同时也涉及到指针的运用。通过解决链表相关的编程问题，面试者可以展示他们对基本数据结构和算法的理解，以及解决问题的能力。

练习题目

反转链表 https://leetcode.cn/problems/reverse-linked-list/description/

查找两个链表的公共节点 https://leetcode.cn/problems/3u1WK4/description/

交换链表中的节点 https://leetcode.cn/problems/swapping-nodes-in-a-linked-list/description/

链表排序 https://leetcode.cn/problems/sort-list/description/

判断是否有环 https://leetcode.cn/problems/linked-list-cycle/description/

输出环的起始位置 https://leetcode.cn/problems/linked-list-cycle-ii/description/

合并两个链表 https://leetcode.cn/problems/merge-two-sorted-lists/description/

合并多个链表 https://leetcode.cn/problems/merge-k-sorted-lists/description/

翻转链表 https://leetcode.cn/problems/UHnkqh/description/

解题技巧

技巧1：新建一个头节点，一般可以用于避免空指针，统一编程思路。

技巧2：链表题很多都可以用双指针的思路解决。