2.3.3 链表
链表应该是面试时被提及最频繁的数据结构。链表的结构很简单，它由指针把若干个结点连接成链状结构。链表的创建、插入结点、删除结点等操作都只需要20行左右的代码就能实现，其代码量比较适合面试。而像哈希表、有向图等复杂数据结构，实现它们的一个操作需要的代码量都较大，很难在几十分钟的面试中完成。另外，由于链表是一种动态的数据结构，其操作需要对指针进行操作，因此应聘者需要有较好的编程功底才能写出完整的操作链表的代码。而且链表这种数据结构很灵活，面试官可以用链表来设计具有挑战性的面试题。基于上述几个原因，很多面试官都特别青睐链表相关的题目。
我们说链表是一种动态数据结构，是因为在创建链表时，无须知道链表的长度。当插入一个结点时，我们只需要为新结点分配内存，然后调整指针的指向来确保新结点被链接到链表当中。内存分配不是在创建链表时一次性完成，而是每添加一个结点分配一次内存。由于没有闲置的内存，链表的空间效率比数组高。如果单向链表的结点定义如下：
struct ListNode
{
int m_nValue;
ListNode＊ m_pNext;
};
那么往该链表的末尾中添加一个结点的C语言代码如下：
void AddToTail（ListNode＊＊ pHead, int value）
{
ListNode＊ pNew = new ListNode（）;
pNew->m_nValue = value;
pNew->m_pNext = NULL;
if（＊pHead == NULL）
{
＊pHead = pNew;
}
else
{
ListNode＊ pNode = ＊pHead;
while（pNode->m_pNext != NULL）
pNode = pNode->m_pNext;
pNode->m_pNext = pNew;
}
}
在上面的代码中，我们要特别注意函数的第一个参数 pHead 是一个指向指针的指针。当我们往一个空链表中插入一个结点时，新插入的结点就是链表的头指针。由于此时会改动头指针，因此必须把 pHead 参数设为指向指针的指针，否则出了这个函数pHead仍然是一个空指针。
由于链表中的内存不是一次性分配的，因而我们无法保证链表的内存和数组一样是连续的。因此如果想在链表中找到它的第i个结点，我们只能从头结点开始，沿着指向下一个结点的指针遍历链表，它的时间效率为O（n）。而在数组中，我们可以根据下标在O（1）时间内找到第i个元素。下面是在链表中找到第一个含有某值的结点并删除该结点的代码：
void RemoveNode（ListNode＊＊ pHead, int value）
{
if（pHead == NULL || ＊pHead == NULL）
return;
ListNode＊ pToBeDeleted = NULL;
if（（＊pHead）->m_nValue == value）
{
pToBeDeleted = ＊pHead;
＊pHead = （＊pHead）->m_pNext;
}
else
{
ListNode＊ pNode = ＊pHead;
while（pNode->m_pNext != NULL
&& pNode->m_pNext->m_nValue != value）
pNode = pNode->m_pNext;
if（pNode->m_pNext != NULL && pNode->m_pNext->m_nValue == value）
{
pToBeDeleted = pNode->m_pNext;
pNode->m_pNext = pNode->m_pNext->m_pNext;
}
}
if（pToBeDeleted != NULL）
{
delete pToBeDeleted;
pToBeDeleted = NULL;
}
}
除了简单的单向链表经常被设计为面试题之外（面试题5“从尾到头输出链表”、面试题13“在O（1）时间删除链表结点”、面试题15“链表中的倒数第k个结点”、面试题16“反转链表”、面试题17“合并两个排序的链表”、面试题 37“两个链表的第一个公共结点”等），链表的其他形式同样也备受面试官的青睐。
● 把链表的末尾结点的指针指向头结点，从而形成一个环形链表（面试题45“圆圈中最后剩下的数字”）。
● 链表中的结点中除了有指向下一个结点的指针，还有指向前一个结点的指针。这就是双向链表（面试题27“二叉搜索树与双向链表”）。
● 链表中的结点中除了有指向下一个结点的指针，还有指向任意结点的指针，这就是复杂链表（面试题26“复杂链表的复制”）。