Linked List链表的面试问题与回答

在这里你会得到一些基本的和提前的链表面试问题和答案。
链接列表碰巧有非常复杂的面试问题。它们通常很小,很强大,但是如果你完全不理解这些原理,它们就会变得复杂。包含链接列表的代码解决方案是快速和更小的。
1。什么是链表?
链表是一组有序的数据元素,每个元素包含一个与它的继承者(通常是它的前身)的链接。
2。你能用图形来表示链表吗?
链接记录的基本数据结构包括3个部分:数据本身,以及与另一个元素的链接。这个特殊的结构通常称为节点。
链表面试问答
三。需要多少指针来实现一个简单链表?
通常可以找到3个指针:
指向记录开始的头指针。
尾部指针,指向列表的最后一个节点。最后一个节点的关键属性是它的后续指针完全指向空(null)。
指向每个节点的指针,指向下一个节点元素。
4。有多少种类型的链表?
单链表、双链表、多重链表、循环链表。
5。如何表示链表节点?
链接列表节点的最简单的表示是使用typedef结构包装数据和链接,并将该结构作为指向下一个节点的节点指针。C中的一个实例表示


/*ll stands for linked list*/
typedef struct ll
{
    int data;
    struct ll *next;
} Node;
1
2
3
4
5
6
/*ll stands for linked list*/
typedef struct ll
{
    int data;
    struct ll *next;
} Node;
 
6。描述在单链表开始时插入数据的步骤。
在链接列表的开头插入数据涉及创建一个新节点,通过将头指针分配给新节点下一个指针和更新指向新节点的头指针来插入新节点。考虑将临时节点插入到列表的第一个节点


Node *head;
void InsertNodeAtFront(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 the head to point to this new node*/
    head = temp;
}
1
2
3
4
5
6
7
8
9
10
11
Node *head;
void InsertNodeAtFront(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 the head to point to this new node*/
    head = temp;
}
 

7。如何在链表末尾插入一个节点?
这个案子有点复杂。这取决于你的实现。如果你有一个尾指针,它很简单。如果没有尾指针,则必须遍历列表直到到达结尾(即下一个指针为NULL),然后创建一个新节点,并使最后一个节点的下一个指针指向新节点。


void InsertNodeAtEnd(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 *traveller = head;
        while (traveler->next != NULL)
            traveler = traveler->next;

        /* 3. update the last node to point to this new node */
        traveler->next = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void InsertNodeAtEnd(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 *traveller = head;
        while (traveler->next != NULL)
            traveler = traveler->next;
 
        /* 3. update the last node to point to this new node */
        traveler->next = temp;
    }
}
 

8。如何在列表中插入随机位置的节点?
如上所述,您将初始生成新节点。当前,如果该位置为一个或列表为空,则将插入初始位置。否则,您将遍历列表,直到到达指定位置或列表结束为止。然后插入这个新节点。在中间插入是困难的情况,因为您必须确保在正确的顺序内完成指针赋值。首先,在插入新节点之前,将新节点设置为节点的下一个指针。然后将节点设置为新节点的目标位置。查看下面的代码得到一个想法。


void InsertNode(int data, int position)
{
   
/* 1. create the new node */
    Node *temp = new Node;
    temp->data = data;
    temp->next = NULL;

    /* check if the position to insert is first or the list is empty */
    if ((position == 1) || (head == NULL))
    {
        // set the new node to point to head
        // as the list may not be empty
        temp->next = head;
        // point head to the first node now
        head = temp;
        return;
    }
    else
    {
        /* 2. traverse to the desired position */
    Node *t = head;
int currPos = 2;

        while ((currPos < position) && (t->next != NULL))
        {
            t = t->next;
            currPos++;
        }

        /* 3. now we are at the desired location */
        /* 4 first set the pointer for the new node */
        temp->next = t->next;
        /* 5 now set the previous node pointer */
        t->next = temp;
    }
}
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
33
34
35
36
37
void InsertNode(int data, int position)
{
   
/* 1. create the new node */
    Node *temp = new Node;
    temp->data = data;
    temp->next = NULL;
 
    /* check if the position to insert is first or the list is empty */
    if ((position == 1) || (head == NULL))
    {
        // set the new node to point to head
        // as the list may not be empty
        temp->next = head;
        // point head to the first node now
        head = temp;
        return;
    }
    else
    {
        /* 2. traverse to the desired position */
    Node *t = head;
int currPos = 2;
 
        while ((currPos < position) && (t->next != NULL))
        {
            t = t->next;
            currPos++;
        }
 
        /* 3. now we are at the desired location */
        /* 4 first set the pointer for the new node */
        temp->next = t->next;
        /* 5 now set the previous node pointer */
        t->next = temp;
    }
}
 

9。如何从链表中删除节点?
下面是在指定位置从列表中删除节点的步骤。
将头部设置为指向头部指向的节点。
遍历所需的位置或直到列表结束;
必须将前一个节点指向下一个节点。
10。如何反转单链表?
首先,将指针(*电流)设置为指向第一节点即电流=头。
向前移动直到当前!= NULL(直到最后)
设置另一个指针(*Next)指向下一个节点,即Next=Wrime>下一个
在一个临时变量(*结果)中存储*Next的引用,即当前-> Next=结果
将结果值与当前结果(即结果=当前)进行交换
现在将当前值与下一个交换。即电流=下一个
返回结果并从步骤2重复
也可以使用递归消除链表,这消除了临时变量的使用。
11。比较链表与动态数组
动态数组是一种数据结构,它连续地分配内存中的所有元素,并保持当前元素数量的计数。如果为动态数组保留的区域被超过,则重新分配和跟踪,这是一个昂贵的操作。
链表与动态数组相比有很多好处。在列表的特定点插入或删除元素是常数时间操作,而在随机位置插入动态数组将需要平均移动一半的元素,而在最坏情况下移动所有元素。
尽管可以通过以某种方式将其槽标记为空来在恒定时间内从数组中删除元素,但这会导致阻碍迭代性能的碎片。
12。什么是循环链表?
在单线性列表的最后一个节点中,链接字段通常包含空引用。一个不太常见的约定是让最后一个节点指向列表的第一个节点;在这种情况下,该列表被称为“圆形”或“循环链接”。
13。单链和双链表的区别是什么?
一个双链表,其节点包含三个字段:一个整数值和两个到其他节点的链接,一个指向前一节点,另一个指向下一节点。而单链表只包含指向下一个节点的点。
14。使用链表的应用程序是什么?
堆栈和队列通常使用链接列表实现,其他应用程序是跳过列表、二叉树、展开链接列表、哈希表、堆、自组织列表。
15。如何删除链表(或)中使用的快速和慢速指针?
最佳解在O(n)时间内运行,并使用O(1)空间。此方法使用两个指针(一个慢指针和一个快速指针)。慢指针一次遍历一个节点,而快速指针遍历一个节点的速度是第一个节点的两倍。如果链表中有循环,最终快速和慢速指针将位于同一个节点。另一方面,如果列表没有循环,很明显快速指针将在慢指针之前到达列表的末尾。因此,我们检测到一个循环。
16。你更喜欢使用一个单链表还是一个双链表来遍历元素列表?
双链表每个节点需要比单链表更多的空间,并且它们的基本操作(如插入、删除)更加昂贵;但是它们通常更容易操作,因为它们允许快速和容易地在两个方向上顺序访问列表。另一方面,双链接列表不能用作持久性数据结构。因此,通过遍历节点列表,双链表将是一个更好的选择。
如果你发现上面列出的问题和答案中有任何错误,请在下面评论。

上一篇: iOS的面试问题与回答
下一篇: Linux的面试问题与回答