链表是最基本的数据结构，面试官也常常用链表来考察面试者的基本能力，而且链表相关的操作相对而言比较简单，也适合考察写代码的能力。链表的操作也离不开指针，指针又很容易导致出错。综合多方面的原因，链表题目在面试中占据着很重要的地位。
1.单向链表的定义
想必大家对数组都非常熟悉，数组在存储空间（内存）上是连续的。因此，我们可以根据偏移量轻易的找到数组中的数据。但数组最大的问题是大小是固定的，很多场景是无法预判需要的空间大小的。
1.1什么是单向链表
链表也是一种线性数据结构，但它最大的优势是可以动态的调整大小。这样，我们再也不用担心应该分配多少空间了。
链表是一种物理存储单元上非连续、非顺序的存储结构，元素的逻辑顺序是通过链表中的指针链接次序实现的
链表在日常开发中通常通过数据结构和指针的方式实现，其中包含一个本数据结构的next指针，用于指向下一个元素，这样指下去，就形成了一个单向链表。如下是数据结构的定义：
为了便于链表的管理和使用，我们在实际定义的时候通常还会定义个专门的链表头，链表头的定义如下：
通过增加一个链表头可以方便链表的管理，同时通过增加的元数据可以很方便的得到一些链表的信息，从而提高效率。这样，整个链表的结构大概如图1所示。
图1单向链表示意图1.2单向链表的接口
单向链表最主要的接口就是初始化、插入元素和删除元素等操作了。当然，为了方便使用，还有返回链表头元素，链表尾元素和链表大小等等。我们这里先看一下几个主要的函数接口。
下面我们给出插入操作的代码实现，其它操作类似，也比较简单，这里就不罗列代码了。具体可以参考本文的配套github库。
2.单向链表的算法（面试题）
关于单向链表的面试题很多，我们这里尽量的都收集过来。目前有些复杂的没有答案，但我们后续会陆续写文章将答案收集起来。
2.1求单链表中结点的个数
这个题目是比较简单的，基本做法就是对单向链表进行遍历。在进行遍历的时候有一个计数的变量，每遍历一个节点，计数增1，直到完成链表的遍历。
2.2单链表反转(leetcode)
将链表中的节点指向反过来，比如原来的指向为1-2-3-4-5，那么反转后为5-4-3-2-1。链表反转其实是调整节点的next指针的指向。具体如图所示。
图2链表反转示意图2.3截取出单链表中的后K个结点（k0）
2.4判断一个单链表中是否有环(若带环，求环的长度和入口点)
2.5去除有序链表中的重复元素(leetcode83)
给定一个有序的链表，删除所有重复的元素，保证每个元素在链表中只出现一次。
2.6合并两个排好序的链表(leetcode21)
2.7链表的中间节点(leetcode)
给定一个带有头结点head的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
输入：[1,2,3,4,5]输出：此列表中的结点3(序列化形式：[3,4,5])返回的结点值为3。(测评系统对该结点序列化表述是[3,4,5])。
2.7删除链表中的节点(leetcode)
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。也就是你仅知道要求被删除的节点。
输入:head=[4,5,1,9],node=5输出:[4,1,9]
解释:给定你链表中值为5的第二个节点，那么在调用了你的函数之后，该链表应变为4-1-9.
链表至少包含两个节点。链表中所有节点的值都是唯一的。给定的节点为非末尾节点并且一定是链表中的一个有效节点。不要从你的函数中返回任何结果。
2.8删除链表的倒数第N个节点(leetcode19)
给定一个链表:1-2-3-4-5,和n=2.
当删除了倒数第二个节点后，链表变为1-2-3-5.
2.9删除链表中的节点(leetcode)
删除链表中等于给定值val的所有节点。
输入:1-2-6-3-4-5-6,val=6输出:1-2-3-4-5
2.10约瑟夫环
约瑟夫环(约瑟夫问题)是一个数学的应用问题：已知n个人(以编号1，2，3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列;他的下一个人又从1开始报数，数到m的那个人又出列;依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后结果+1即为原问题的解。
2.11遍历一次，删除倒数第k个结点（k从1开始），不能用替换删除法
2.12将链表后k个节点移到链表头
给一个链表和整数k，将后k个节点移到链表头。
输入：1-2-3-4-5-NULL,k=2,输出：4-5-1-2-3-NULL.
2.13逆序打印单链表
2.14不允许遍历链表,在pos之前插入
2.15单链表的冒泡排序
2.16旋转单链表
题目：给定一个链表，旋转链表，使得每个节点向右移动k个位置，其中k是一个非负数。
输入：1-2-3-4-5-NULL给定值k=2,输出：4-5-1-2-3-NULL.
2.17划分链表
题目：按某个给定值将链表划分为左边小于这个值，右边大于这个值的新链表如一个链表为1-4-5-2给定一个数3则划分后的链表为1-2-4-5
2.18链表相加求和
题目：假设链表中每一个节点的值都在0-9之间，那么链表整体可以代表一个整数。
例如：9-3-7可以代表
给定两个这样的链表，头节点为head1head2生成链表相加的新链表。
如9-3-7和6-3生成的新链表应为1-0-0-0
2.19重排链表
题目给定一个单链表L：L0→L1→…→Ln-1→Ln,重新排列后为L0→Ln→L1→Ln-1→L2→Ln-2→…要求必须在不改变节点值的情况下进行原地操作。