跳转至

3.3 链表

链表应该是面试时被提及最频繁的数据结构。

链表的结构很简单,它由指针把若干个节点连接成链状结构。

链表的创建,插入节点,删除节点等操作都只需要20行左右的代码就能实现,其代码量比较适合面试。

而像哈希表,有向图等复杂数据结构,实现它们的一个操作需要的代码量都比较大,很难在几十分钟的面试中完成。

另外,由于链表是一种动态的数据结构,其需要对指针进行操作,因此应聘者需要很好的编程功底才能写出完整的操作链表的代码。

而且链表这种数据结构很灵活,面试官可以用链表来设计具有挑战性的面试题。 基于上述几个原因,很多面试官都特别青睐与链表相关的题目。

我们说链表是一种动态数据结构,是因为在创建链表时,无须知道链表长度,当插入一个节点时,我们只需要为新节点分配内存,然后调整指针指向来确保新节点被链接到链表当中。

内存分配不是在创建链表时一次性完成的,而是每添加一个节点分配一次内存。 由于没有闲置的内存,链表的空间效率比数组高。

如果单向链表的节点定义如下:

struct Node
{
    int value;
    Node* next;
};

那么往该链表末尾添加一个节点的c++代码如下:

void AddToTail(Node **pHead, int value)
{
    Node* node = new Node();
    node->value = value;
    node->next = nullptr;

    // 如果head为nullptr, 则追加的元素为第一个元素
    if (*pHead == nullptr)
    {
        *pHead = node;
    }
    else
    {
        Node* cur = *pHead;

        while (cur->next != nullptr)
            cur = cur->next;

        cur->next = node;
    }
}
在上面的代码中,我们要特别注意函数的第一个参数pHead是一个指向指针的指针。当我们往一个空链表中插入一个节点时,新插入的节点就是链表的头指针。

由于此时会改动头指针,因此必须把pHead参数设为指向指针的指针,否则出了这个函数pHead仍然是一个空指针。

由于链表中的内存不是一次性分配的,因而我们无法保证链表的内存和数组一样是连续的。

因此,如果想在链表中找到它的第i个节点,那么我们只能从头节点开始,沿着指向下一个节点的指针遍历链表,它的时间效率为O(n)。

下面是在链表中找到第一个含有某值的节点并删除该节点的代码。

void RemoveNode(Node** pHead, int value)
{
    // 空链表
    if (pHead == nullptr || *pHead == nullptr)
        return;

    Node* pre = *pHead;
    if (pre->value == value)
    {
        if (pre->next != nullptr)
            *pHead = pre->next;
        else
            *pHead = nullptr;
        return;
    }

    if (pre->next == nullptr)
        return;

    Node* cur = pre->next;
    while (cur != nullptr)
    {
        if (cur->value == value)
        {
            pre->next = cur->next;
            return;
        }
        else
        {
            pre = pre->next;
            cur = pre->next;
        }
    }
}

完整的参考代码: LinkList.cpp

除了简单的单向链表经常被设计为面试题(详见面试题6,面试题18, 面试题22,面试题24,面试题25,面试题52等),

链表的其他形式也备受面试官的青睐。

  • 把链表的末尾节点的指针指向头节点,从而形成一个环形链表(详见面试题62)
  • 链表中的节点中除了有指向下一个节点的指针,还有指向前一个节点的指针。 这就是双向链表(详见面试题36)
  • 链表中的节点中除了有指向下一个节点的指针,还有指向任意节点的指针,这就是复杂链表。(详见面试题35)

面试题6: 从尾到头打印链表

Question

输入一个链表的头节点,从尾到头反过来打印出每个节点的值,链表节点定义如下。

struct Node
{
    int value;
    Node* next;
};

看到这道题后,很多人的第一反应是从头到尾输出将会比较简单,于是我们很自然的想到把链表中的链接节点反转过来,改变链表的方向,然后就可以从头到尾输出了。

但是该方法会改变原链表的结构。 是否允许在打印链表的时候修改链表的结构? 这取决于面试官的要求,因此在面试的时候我们要询问清楚面试官的要求。

Tip

在面试中,如果我们打算修改输入的数据,则最好先问面试官是不是允许修改。

通常打印是一个只读操作,我们不希望打印时修改内容。假设面试官也要求不能改变链表的结构。

接下来我们想到解决这个问题肯定要遍历链表。 遍历的顺序是从头到尾,可输出的顺序确是从尾到头,也就是说,第一个遍历的节点最后一个输出,而最后一个面试的节点要第一个输出。这就是典型的”先进后出“,我们可以用栈实现这种循序。每经过一个节点的时候,把该节点放到栈中。当遍历完整个链表后,再从栈顶开始逐个输出节点的值。

Answer

  1. 栈实现
    void PrintLinkReversed(Node* Head)
    {
        stack<Node*> nodes;
        Node* cur = Head;
    
        while (cur != nullptr)
        {
            nodes.push(cur);
            cur = cur->next;
        }
    
        while (!nodes.empty())
        {
            cur = nodes.top();
            cout << cur->value << ' ';
            nodes.pop();
        }
        cout << endl;
    }
    
  2. 递归实现
    void PrintLinkReversed(Node* Head)
    {
        if (Head == nullptr)
            return;
        else
        {
            PrintLinkReversed(Head->next);
            if (Head != nullptr)
                cout << Head->value << ' ';
        }
    }
    
    上面的基于递归的代码看起来简洁,但是有一个问题,当链表非常长的时候,就会导致函数调用的层级很深,从而有可能导致函数调用栈溢出。

PrintListReversed1.cpp

PrintListReversed2.cpp

本题考点

  • 考查应聘者对单向链表的理解和编程能力
  • 考查应聘者对循环,递归和栈3个相互关联的概念的理解