单向链表的概念及面试题大全


链表是最基本的数据结构,面试官也常常用链表来考察面试者的基本能力,而且链表相关的操作相对而言比较简单,也适合考察写代码的能力。链表的操作也离不开指针,指针又很容易导致出错。综合多方面的原因,链表题目在面试中占据着很重要的地位。

1. 单向链表的定义

想必大家对数组都非常熟悉,数组在存储空间(内存)上是连续的。因此,我们可以根据偏移量轻易的找到数组中的数据。但数组最大的问题是大小是固定的,很多场景是无法预判需要的空间大小的。

1.1 什么是单向链表

链表也是一种线性数据结构,但它最大的优势是可以动态的调整大小。这样,我们再也不用担心应该分配多少空间了。

链表是一种物理存储单元上非连续、非顺序的存储结构,元素的逻辑顺序是通过链表中的指针链接次序实现的

链表在日常开发中通常通过数据结构和指针的方式实现,其中包含一个本数据结构的next指针,用于指向下一个元素,这样指下去,就形成了一个单向链表。如下是数据结构的定义:

1
2
3
4
5
struct list_node
{
void *data; /* 存储的数据,通过void指针,可以适配多种数据类型 */
struct list_node *next; /* 指向下一个节点,如果为尾节点则指向NULL */
};

为了便于链表的管理和使用,我们在实际定义的时候通常还会定义个专门的链表头,链表头的定义如下:

1
2
3
4
5
6
7
struct list
{
int size;
void (*print_node)(void *data);
struct list_node *head;
struct list_node *tail;
};

通过增加一个链表头可以方便链表的管理,同时通过增加的元数据可以很方便的得到一些链表的信息,从而提高效率。这样,整个链表的结构大概如图1所示。

图1 单向链表示意图

1.2 单向链表的接口

单向链表最主要的接口就是初始化、插入元素和删除元素等操作了。当然,为了方便使用,还有返回链表头元素,链表尾元素和链表大小等等。我们这里先看一下几个主要的函数接口。

1
2
3
4
5
6
/*  初始化链表 */
void list_init(struct list *list, void (*print_node)(void *data));
/* 向链表中添加一个元素,其中node为插入的位置,也就是
插到该元素的后面,如果node为NULL则插到首节点。 */
int list_insert_next(struct list *list, struct list_node *node, void *data);
int list_rem_next(struct list *list, struct list_node *node, void **data);

下面我们给出插入操作的代码实现,其它操作类似,也比较简单,这里就不罗列代码了。具体可以参考本文的配套github库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int list_insert_next(struct list *list, 
struct list_node *node,
void *data)
{
struct list_node *new_node;

if (NULL == list) {
return -1;
}

new_node = (struct list_node*)malloc(sizeof(struct list_node));
if (NULL == new_node) {
return -1;
}

new_node->data = data;
if (NULL == node) {
if (list_size(list) == 0)
list->tail = new_node;
new_node->next = list->head;
list->head = new_node;
} else {
if (NULL == node->next) {
list->tail = new_node;
}
new_node->next = node->next;
node->next = new_node;
}

list->size ++;
return 0;
}

2. 单向链表的算法(面试题)

关于单向链表的面试题很多,我们这里尽量的都收集过来。目前有些复杂的没有答案,但我们后续会陆续写文章将答案收集起来。

2.1 求单链表中结点的个数

这个题目是比较简单的,基本做法就是对单向链表进行遍历。在进行遍历的时候有一个计数的变量,每遍历一个节点,计数增1,直到完成链表的遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int list_node_count(struct list *list)
{
int ret = 0;
struct list_node *cur_node;
/* 注意list指针非法的情况 */
if (NULL == list) {
return ret;
}

cur_node = list->head;
while (cur_node) {
ret ++;
cur_node = cur_node->next;
}
return ret;
}

2.2 单链表反转 (leetcode 206)

将链表中的节点指向反过来,比如原来的指向为1->2->3->4->5,那么反转后为5->4->3->2->1。链表反转其实是调整节点的next指针的指向。具体如图所示。
图2 链表反转示意图

2.3 截取出单链表中的后K个结点(k>0)

2.4 判断一个单链表中是否有环(若带环,求环的长度和入口点)

2.5 去除有序链表中的重复元素(leetcode 83)

给定一个有序的链表,删除所有重复的元素,保证每个元素在链表中只出现一次。

2.6 合并两个排好序的链表(leetcode 21)

2.7 链表的中间节点(leetcode 876)

给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。

输入:[1,2,3,4,5]
输出:此列表中的结点 3 (序列化形式:[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。

2.7 删除链表中的节点 (leetcode 237)

请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点。也就是你仅知道要求被删除的节点。

输入: head = [4,5,1,9], node = 5
输出: [4,1,9]

解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.

链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。

2.8 删除链表的倒数第N个节点(leetcode 19)

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.

2.9 删除链表中的节点(leetcode 203)

题目
删除链表中等于给定值 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 可以代表 937
给定两个这样的链表,头节点为 head1 head2 生成链表相加的新链表。
如 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→… 要求必须在不改变节点值的情况下进行原地操作。