链表面试题

2025年3月17日 | 阅读13分钟

以下列出了顶部的、最常被问到的**链表面试题**及答案。

1) 简要解释一下链表。

链表可以被定义为一种线性数据结构，它可以存储一系列项。换句话说，链表可用于存储各种相似类型的对象。列表中的每个元素或单元都称为节点。每个节点包含其自身的数据以及指向下一个节点的地址。它类似于一个链条。链表用于创建图和树。

2) 如何在图形视图中表示链表？

链表可以被定义为一种数据结构，其中每个元素都是一个独立的物体。链表元素不存储在连续的位置。指针用于连接链表中的元素。

列表中的每个节点由两部分组成——**数据本身**和**指向序列中下一个节点的引用（也称为链接）**。最后一个节点包含指向 null 的引用。链表的起始点称为列表的头部（head）。需要注意的是，head 指向的是第一个节点，而不是一个独立的节点。如果列表为空，则 head 被视为 null 引用。

3) 有多少种类型的链表？

有多种类型的链表可用。

单向链表
双向链表
多重链表
循环链表

4) 简要解释一下单向链表。

单向链表包含节点，这些节点包含一个数据字段和一个 next 字段。next 字段进一步指向节点序列中的下一个节点。

换句话说，单向链表中的节点包含一个指向列表中下一个节点的指针。我们可以在单向链表中执行插入、删除和遍历等操作。

下图显示了一个单向链表，其节点包含两个字段：一个整数值和一个指针值（指向下一个节点的链接）。

5) 你对双向链表有什么了解？

双向链表包含一个指向下一个节点的指针（链接）以及指向列表中前一个节点的指针。节点之间的两个链接可以称为“前向”和“后向”，或“next”和“prev（previous）”。下图显示了一个双向链表，其节点包含三个字段：一个整数值、一个指向下一个节点的链接，以及一个指向前一个节点的链接。

一种技术（称为**XOR 链接**）用于仅用每个节点中的一个链接字段来实现双向链表。但是，这项技术需要更多的能力来执行一些关于地址的操作，因此对于某些高级语言可能不可用。

大多数现代操作系统使用双向链表来维护对活动线程、进程和其他动态对象的引用。

6) 简要解释一下多重链表。

在多重链表中，每个节点包含两个或多个链接字段。每个字段用于以不同的顺序连接同一组记录，例如“按姓名、按出生日期、按部门”等。

7) 如何解释循环链表？

在链表的最后一个节点中，链接字段通常包含一个 null 引用。在循环链表中，最后一个节点不包含 null 指针，而是包含一个指向第一个节点的指针。在这种情况下，该列表被称为“循环链接”；否则，它被称为“开放”或“线性”。循环链表是一种列表，其中最后一个指针指向或包含第一个节点的地址。

在循环双向链表中，第一个节点也指向列表的最后一个节点。

8) 实现一个简单的链表需要多少个指针？

通常需要三种类型的指针来实现一个简单的链表：

一个“head”指针，用于指向列表中记录的起始位置。
一个“tail”指针，用于指向最后一个节点。最后一个节点的关键之处在于其后续指针指向空（NULL）。
每个节点中的一个指针，用于指向下一个节点元素。

9) 如何表示链表节点？

表示链表节点的最简单方法是使用**typedef 结构**将数据和链接封装起来。然后将该结构进一步分配给一个指向下一个节点的 Node 指针。

在 C 语言中表示的一个例子可以定义为：

/*ll stands for linked list*/
typedefstructll
{
int data;
structll *next;
} Node

10) 链表通常使用哪种内存分配方式？

链表通常使用动态内存分配。

11) 你对链表的遍历有什么了解？

“遍历”一词指的是处理列表中每个元素的操作。

12) 链表和线性数组之间的主要区别是什么？

链表	线性数组
插入和删除很容易。	插入和删除很困难。
链表在执行插入和删除时不需要移动节点。	线性数组在执行插入和删除时需要移动节点。
在链表中，空间不会被浪费。	在线性数组中，空间会被浪费。
链表不昂贵。	线性数组有点昂贵。
它可以根据需要进行扩展或缩减。	它不能缩减或扩展。
要访问链表中的每个元素，需要不同的时间。	要访问线性数组中的每个元素，需要相同的时间。
链表中的元素可能存储在连续的内存位置，也可能不存储。	元素存储在连续的内存位置。
要到达特定节点，我们需要遍历该特定节点之前的所有节点。	我们可以直接到达任何特定元素。

13) 链表中的虚拟头节点（dummy header）包含什么？

在链表中，虚拟头节点包含实际数据的第一个记录。

14) 列出链表的一些应用？

链表的一些主要应用如下：

链表允许我们实现队列、栈、图等。
链表允许我们在列表的开头和结尾插入元素。

15) 如何将一个节点插入到单向链表的开头？

要将节点插入到列表的开头，我们需要遵循以下步骤：

创建一个新节点。
通过将 head 指针分配给新节点的 next 指针来插入新节点。
更新 head 指针以指向新节点。

Node *head;
voidInsertNodeAtFront(int data)
{
/* 1. create the new node*/
Node *temp = new Node;
temp->data = data;
/* 2. insert it at the first position*/
temp->next = head;
/* 3. update head to point to this new node*/
head = temp;
}

16) 列举一些使用链表的应用程序。

队列和栈都可以使用链表实现。其他一些使用链表的应用程序包括二叉树、跳表、展开链表、哈希表等。

17) 单向链表和双向链表有什么区别？

双向链表节点包含三个字段：一个整数值和两个指向其他两个节点的链接（一个指向前一个节点，另一个指向下一个节点）。

另一方面，单向链表包含一个仅指向下一个节点的链接。

18) 链表的主要优点是什么？

链表的主要优点是我们不需要为列表指定固定大小。我们向链中添加的元素越多，链就越长。

19) 如何将一个项目添加到列表的开头？

将一个项目添加到列表的开头，我们需要遵循以下步骤：

创建一个新项目并设置其值。
将新创建的项目链接到列表的头部。
将列表的头部设置为我们的新项目。

如果我们使用一个函数来执行此操作，我们需要修改 head 变量。

20) 如何在链表的末尾插入一个节点？

这种情况有点困难，因为它取决于实现类型。如果我们有一个尾指针，那么它很简单。如果我们没有尾指针，我们就必须遍历列表直到到达末尾（即，next 指针为 NULL）。然后我们需要创建一个新节点，并让最后一个节点的 next 指针指向新节点。

voidInsertNodeAtEnd(int data)
{
   /* 1. create the new node*/
    Node *temp = new Node;
temp->data = data;
temp->next = NULL;
    /* check if the list is empty*/
if (head == NULL)
    {
head = temp;
return;
    }
else
    {
        /* 2. traverse the list till the end */
        Node *traveler = head;
while (traveler->next != NULL)
traveler = traveler->next;
        /* 3. Set up the last node to point to this new node*/
traveler->next = temp;
    }
}

21) 如何在链表的随机位置插入一个节点？

如果我们想在第一个位置或空列表中插入一个节点，我们可以轻松地插入该节点。否则，我们需要遍历列表直到到达指定位置或列表末尾。然后我们可以插入一个新节点。在中间位置插入一个节点有点困难，因为我们必须确保以正确的顺序执行指针赋值。要在中间插入一个新节点，请遵循以下步骤：

首先，我们需要将新节点的 next 指针设置为它之前的那个节点。
然后，我们需要将前一个节点的 next 指针分配给新节点的起始位置。

请查看下面的示例。

voidInsertNode(int data, int position)
{
/* 1. create the new node */
    Node *temp = new Node;
temp->data = data;
temp->next = NULL;
    /* confirm if the position to insert is first or the list is empty */
if ((position == 1) || (head == NULL))
    {
        // set up the new node pointing to head
        // because list may not be empty
temp->next = head;
        // Now point head to the first node
head = temp;
return;
    }
else
    {
   /* 2. traverse to the required position */
    Node *t = head;
intcurrPos = 2;
while ((currPos< position) && (t->next != NULL))
        {
            t = t->next;
currPos++;
        }
 /* 3. now we are at the required location */
        /* 4 first set up the pointer for the new node */
temp->next = t->next;
        /* 5 now set up the previous node pointer */
t->next = temp;
    }
}

22) 如何从单向链表中删除第一个节点？

要从单向链表中删除第一个节点，我们需要遵循以下步骤：

将第一个节点的地址复制到某个临时变量。
将 head 更改为链表的第二个节点。
删除第一个节点与第二个节点的连接。
删除临时变量并释放第一个节点占用的内存。

23) 如何从链表中删除任何特定节点？

如果要删除的节点是根节点，则可以轻松删除它。要删除中间节点，我们必须有一个指向我们要删除的节点之前的节点的指针。所以如果位置不是零，那么我们就运行一个位置循环，得到前一个节点的指针。

以下步骤用于从列表中指定位置删除节点：

将 head 设置为指向 head 当前指向的那个节点。
遍历列表直到所需位置或列表末尾（以先到者为准）。
我们需要将前一个节点指向下一个节点。

24) 如何反转单向链表？

要反转单向链表，我们需要遍历列表。我们需要在每一步反转链接，例如在第一次迭代之后，head 将指向 null，下一个元素将指向 head。当我们在遍历结束时到达链表的尾部时，尾部将开始指向倒数第二个元素，并成为新的 head。这是因为我们可以从该特定节点进一步遍历所有元素。

以下步骤可用于反转单向链表：

首先，我们需要设置一个指针（*current）指向第一个节点（即 current=head）。
前进直到 current != null（直到列表末尾）。
设置另一个指针（*next）指向下一个节点（即 next=current->next; current->next=result;）。
在临时变量（*result）中保留 *next 的引用，即 current->next=result。
交换 result 值和 current，即 result=current。
然后交换 current 值和 next，即 current=next。
返回 result 并从步骤 2 开始重复。

链表也可以通过递归反转，这样可以省去使用临时变量。

25) 如何在链表中删除环？快慢指针的作用是什么？

检测和删除链表中环的主要概念是使用两个指针（一个慢指针和一个快指针）。慢指针一次遍历一个节点，而快指针的速度是慢指针的两倍。如果链表包含环，快指针和慢指针将在同一节点。另一方面，如果列表不包含环，那么快指针显然会比慢指针先到达末尾。如果这两个指针相遇，则检测到环。如果检测到环，环的起始点可以帮助我们删除链表中检测到的环。它被称为**Floyd 循环查找算法**。下图显示了链表中的环是什么样子。

26) 在单向链表和双向链表之间，你会选择哪一个来遍历元素列表？

与单向链表相比，双向链表每个节点需要更多的空间。在双向链表中，基本的插入和删除操作成本更高，但它们更容易操作，因为它们提供了在两个方向上对列表进行快速简便的顺序访问。但是，双向链表不能用作持久数据结构。因此，双向链表将是遍历节点列表的更好选择。

27) 在链表中插入新节点时，空闲节点在哪里可用？

如果在一个链表中插入了一个新节点，空闲节点可以在**可用列表（Avail List）**中找到。

28) 对于哪个头列表，最后一个节点包含 null 指针？

对于接地头列表（grounded header list），最后一个节点将包含 null 指针。

29) 如何在 Java 中遍历链表？

有几种方法可以在 Java 中遍历链表，例如，我们可以使用传统的 for、while 或 do-while 循环，并通过链表进行迭代，直到到达链表末尾。或者，我们可以使用 Java 1.5 的增强 for 循环或迭代器来遍历 Java 中的链表。从 JDK 8 开始，我们可以选择使用 **java.util.stream.Stream** 来遍历链表。

30) 如何计算 Java 中单向链表的长度？

我们可以迭代链表并计算节点数，直到到达链表末尾，此时下一个节点将为 null。计数器的值被视为链表的长度。

31) 如何从第一个到最后一个显示单向链表？

要从第一个到最后一个显示单向链表，必须遵循以下步骤：

使用 create() 创建一个链表。
存储在全局变量“start”中的地址不能更改，因此必须声明一个类型为 node 的临时变量“temp”。
要从开始到结束进行遍历，应将起始节点的地址分配给指针变量，即 temp。

struct node *temp;  //Declare temp variable
temp = start;       //Assign Starting Address to temp

如果 temp 为 NULL，则表示已访问最后一个节点。

while(temp!=NULL)
{
printf("%d",temp->data);
temp=temp->next;
}

32) 列出链表的一些缺点。

链表的一些重要缺点如下：

不允许随机访问。我们需要从第一个节点开始按顺序访问元素。因此，我们不能使用链表进行二分搜索。
每个列表元素都需要更多的指针内存空间。
缓慢的 O(n) 索引访问，因为通过索引访问链表意味着我们需要递归地循环遍历列表。
局部性差，链表使用的内存分散且混乱。

33) 提到 Java 中用于 LinkedList 类的包。

Java 中用于 LinkedList 的包是 **java.util**。

34) 提到 Java 中 LinkedList 实现的一些接口。

Java LinkedList 实现的一些主要接口是：

Serializable
Queue
列表
Cloneable
集合
Deque
Iterable

35) 如何在 Java 中使用 Stack 来计算两个链表的和？

要计算链表的和，我们计算相同位置节点上存储的值的和。**例如**，我们将两个链表中第一个节点的值相加，以找到结果链表中第一个节点的值。如果两个链表的长度不相等，那么我们只添加较短链表中的元素，并将较长链表中剩余节点的剩余值复制过来。

面试技巧	招聘/HR 面试问题
JavaScript面试题	jQuery面试问题
Java 基础面试问题	Java OOPs 面试问题
Servlet面试题	JSP面试题
Spring 面试问题	Hibernate面试题
PL/SQL 面试问题	SQL面试题
Oracle 面试问题	Android 面试问题
SQL Server 面试问题	MySQL 面试问题

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

所有面试

公司面试