【地铁上的面试题】--基础部分--数据结构与算法--数组和链表

零、章节简介

《数据结构与算法》是《地铁上的面试题》专栏的第一章，重点介绍了技术面试中不可或缺的数据结构和算法知识。数据结构是组织和存储数据的方式，而算法是解决问题的步骤和规则。
这一章的内容涵盖了常见的数据结构和算法，包括数组和链表、栈和队列、树和图，以及排序和搜索算法等。通过深入学习和理解这些基础概念，读者将能够优化代码、提高算法效率，并解决面试中常见的编程问题。
每个主题都将提供清晰的解释、示例代码和常见面试题。读者将学习如何选择和实现合适的数据结构，如何运用常用算法来解决实际问题，以及如何分析和优化算法的时间和空间复杂度。
无论你是准备面试还是想夯实基础知识，这一章都将为你打下坚实的数据结构与算法基础。通过在地铁上的学习，你将能够在面试中展现出自信和高效的解决问题能力。让我们一起踏上数据结构与算法的旅程！

一、概念

1.1 数据结构的基本概念

数据结构是计算机科学中研究数据组织、存储和管理方式的基本概念。它关注数据元素之间的关系以及操作这些数据元素的方法。数据结构可以分为两种基本类型：线性结构和非线性结构。线性结构中的数据元素之间存在一对一的关系，如数组和链表；而非线性结构中的数据元素之间存在一对多或多对多的关系，如树和图。数据结构的设计和选择对于解决实际问题和优化算法效率至关重要。常见的数据结构包括数组、链表、栈、队列、树、图等。每种数据结构都有自己的特点和适用场景，具体选择要考虑数据操作的效率、空间占用、插入和删除的复杂度等因素。
理解数据结构的基本概念有助于编写高效的程序、解决实际问题和应对技术面试。它为我们提供了组织和管理数据的工具，使得我们能够更好地利用计算机的处理能力。

1.2 数组和链表的定义和特点

数组和链表是常见的数据结构，用于组织和存储数据。它们具有不同的定义和特点。
数组是一种线性数据结构，由一组连续的内存空间组成，用于存储相同类型的数据元素。数组的定义包括元素类型和固定大小。元素可以通过索引访问，索引从0开始。数组的特点包括：

1. 随机访问：可以通过索引直接访问数组中的元素，具有常数时间复杂度O(1)。
2. 连续存储：数组的元素在内存中连续存储，便于读取和缓存。
3. 固定大小：数组的大小在创建时确定，不易动态改变。

链表是一种动态数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的引用。链表的定义包括头节点和尾节点（在双向链表中还包括指向上一个节点的引用）。链表的特点包括：

1. 动态性：链表的长度可以动态增长或缩小，灵活性较高。
2. 插入和删除：在链表中插入和删除节点较为高效，只需调整节点的引用。
3. 随机访问复杂度高：想要访问链表中的特定节点，需要从头节点开始遍历，时间复杂度为O(n)。

根据应用场景和需求，选择数组或链表有不同的考量。数组适合随机访问和已知大小的情况，例如需要频繁访问元素或索引操作的场景。链表适用于频繁的插入和删除操作，以及动态大小的情况。

二、数组

2.1 数组的基本原理和特点

数组是一种基本的数据结构，它在计算机科学中被广泛使用。数组的基本原理是将一组相同类型的元素按照顺序存储在连续的内存空间中。每个元素在内存中占据固定的大小，并可以通过索引访问。
数组的特点是由于元素在内存中连续存储，使得数组具有以下优势和特点：

• 快速访问：由于元素的连续存储，可以通过索引直接访问数组中的元素，时间复杂度为常数O(1)。这种随机访问的能力使得数组适合在特定位置查找或修改元素。
• 简单而高效的存储：数组的存储是紧凑的，每个元素占据相同的固定大小。这样的特点使得数组在存储大量数据时具有高效性，不会出现额外的空间浪费。
• 顺序访问：由于元素在内存中的连续性，数组在顺序访问数据时表现出很好的性能，因为可以有效地利用CPU缓存。
• 多维支持：数组还可以具有多维结构，例如二维数组、三维数组等。这种多维数组的特点使得数组可以方便地表示矩阵、图像等复杂数据结构。

然而，数组也有一些限制和缺点：

• 固定大小：数组在创建时需要指定大小，并且大小通常是固定的，难以动态改变。如果需要增加或减少元素的数量，可能需要重新分配更大的内存空间并复制数据。
• 插入和删除低效：由于数组的连续存储特性，插入和删除元素需要移动其他元素，导致操作的时间复杂度为O(n)，其中n是元素的数量。

TIP：数组作为一种基本的数据结构，具有快速访问、简单高效的存储和顺序访问的优点。然而，由于固定大小和低效的插入删除操作，需要在特定的应用场景中进行选择和权衡。

2.2 数组的插入、删除和查找操作

数组的插入、删除和查找操作是常见的数组操作，它们的时间复杂度和空间复杂度如下所示：

1. 插入操作：
   • 最好情况时间复杂度：O(1)。当要插入的元素位于数组的末尾时，只需将元素放入指定位置即可。
   • 最坏情况时间复杂度：O(n)。当要插入的元素位于数组的开头时，需要将数组中的所有元素后移，以腾出空间。
   • 平均情况时间复杂度：O(n)。考虑所有可能的插入位置，插入的元素可能位于数组的任何位置。

   void insertElement(int arr[], int size, int index, int element) {
       if (index >= size || index < 0) {
           printf("无效的插入位置\n");
           return;
       }
       for (int i = size - 1; i > index; i--) {
           arr[i] = arr[i - 1];
       }
       arr[index] = element;
   }
1
2
3
4
5
6
7
8
9
10

2. 删除操作：
   • 最好情况时间复杂度：O(1)。当要删除的元素位于数组的末尾时，只需将末尾元素置为无效值。
   • 最坏情况时间复杂度：O(n)。当要删除的元素位于数组的开头时，需要将数组中的所有元素前移，以填补空缺。
   • 平均情况时间复杂度：O(n)。考虑所有可能的删除位置，删除的元素可能位于数组的任何位置。

  void deleteElement(int arr[], int size, int index) {
      if (index >= size || index < 0) {
          printf("无效的删除位置\n");
          return;
      }
      for (int i = index; i < size - 1; i++) {
          arr[i] = arr[i + 1];
      }
      arr[size - 1] = 0; // 或其他无效值
  }
1
2
3
4
5
6
7
8
9
10

3. 查找操作：
   • 最好情况时间复杂度：O(1)。当要查找的元素位于数组的第一个位置时，只需一次比较即可找到。
   • 最坏情况时间复杂度：O(n)。当要查找的元素位于数组的最后一个位置或不存在于数组中时，需要比较整个数组。
   • 平均情况时间复杂度：O(n)。

   int searchElement(int arr[], int size, int element) {
       for (int i = 0; i < size; i++) {
           if (arr[i] == element) {
               return i;
           }
       }
       return -1; // 表示元素未找到
   }
1
2
3
4
5
6
7
8

在以上示例中，假设数组 arr[] 的大小为 size。插入和删除操作涉及元素的移动，查找操作通过遍历数组进行比较。空间复杂度为数组的大小，即 O(n)。

2.3 数组的应用场景和注意事项

数组在编程中有广泛的应用场景，以下是一些常见的应用场景和注意事项：
应用场景：

1. 存储和访问数据：数组是一种用于存储和访问大量数据的有效方式，例如存储学生成绩、图像像素、音频样本等。
2. 算法和数据结构：许多经典的算法和数据结构都是基于数组设计的，如排序算法、堆、哈希表等。
3. 缓存和缓冲区：数组可用于实现缓存和缓冲区，提高数据访问效率，如文件缓冲区、图像缓存等。
4. 矩阵和多维数据：数组的多维特性使其适用于表示矩阵、图形、地图等复杂数据结构。

注意事项：

1. 需要预先确定大小：数组在创建时需要指定大小，且大小通常是固定的。因此，在使用数组时需确保足够的内存空间，避免溢出或浪费。
2. 越界检查：数组的索引从0开始，应谨慎处理索引越界问题，以避免访问无效内存位置或数据损坏。
3. 插入和删除的开销较大：由于插入和删除元素需要移动其他元素，可能导致性能下降。若需频繁进行插入和删除操作，可能需要考虑其他数据结构。
4. 内存连续性限制：由于数组要求内存连续存储，当需要大块连续内存时，可能受到内存碎片和可用内存大小的限制。
5. 数据类型和大小一致性：数组中的元素类型应保持一致，不支持存储不同类型的数据。同时，数组的大小可能限制存储的元素数量。

Tip：使用数组时需要根据具体情况权衡其优势和限制。若需要频繁的随机访问和已知大小的存储，数组是一个不错的选择。但在涉及频繁插入和删除、动态大小变化的情况下，可能需要考虑其他数据结构的使用。

三、链表

3.1 链表的基本原理和特点

链表是一种常见的数据结构，用于存储和组织数据。它的基本原理是通过节点之间的指针连接来表示数据的逻辑顺序。

链表由一系列节点组成，每个节点包含数据和指向下一个节点的引用（在双向链表中还包括指向上一个节点的引用）。链表的特点如下：

• 动态性：链表的长度可以动态增长或缩小，不需要事先指定大小。这使得链表在需要频繁插入和删除元素的场景下非常灵活。
• 灵活的内存分配：链表使用动态内存分配，节点可以分散在内存的不同位置。这与数组不同，不需要一块连续的内存空间，避免了固定大小的限制和内存浪费。
• 插入和删除操作高效：在链表中插入或删除节点的操作相对高效，只需要调整节点之间的引用指针即可，不需要移动其他节点。时间复杂度通常为O(1)。
• 随机访问复杂度高：链表的访问需要从头节点开始按顺序遍历，直到找到目标节点。这导致了随机访问的时间复杂度为O(n)，其中n是链表的长度。
• 支持循环结构：链表可以形成循环结构，即尾节点的引用指向头节点，从而创建环形链表。

链表的灵活性和高效的插入、删除操作使其在许多场景中得到广泛应用，例如实现队列、栈、图等数据结构，以及在内存受限或需要频繁插入和删除的情况下。然而，链表的随机访问复杂度较高，不适合需要频繁随机访问元素的场景。选择链表还是其他数据结构应根据具体需求和性能考虑做出权衡。

3.2 单向链表、双向链表和循环链表的区别

单向链表、双向链表和循环链表是链表的三种常见形式，它们之间有以下区别：

1. 单向链表（Singly Linked List）：

   • 每个节点包含数据和指向下一个节点的引用。
   • 节点只能从前往后遍历，不能回溯到前一个节点。
   • 最后一个节点的引用指向空（NULL）表示链表的结束。

   

2. 双向链表（Doubly Linked List）：

   • 每个节点包含数据、指向下一个节点的引用和指向前一个节点的引用。
   • 可以从前往后或从后往前遍历链表，具有双向遍历的能力。
   • 第一个节点的前驱引用和最后一个节点的后继引用指向空。
     

3. 循环链表（Circular Linked List）：

   • 每个节点包含数据和指向下一个节点的引用。
   • 最后一个节点的引用指向第一个节点，形成一个循环结构。
   • 可以从任何节点开始遍历整个链表。
     

区别总结：

• 单向链表只有一个指向后继节点的引用，双向链表则有指向前驱和后继节点的引用，循环链表具有循环连接。
• 单向链表只能从前往后遍历，而双向链表和循环链表可以双向遍历。
• 单向链表的最后一个节点的引用为空，而双向链表的最后一个节点的后继引用为空，循环链表中最后一个节点的引用指向第一个节点，形成循环结构。

Tip：根据具体的应用需求和操作特点，选择适合的链表类型。单向链表适用于仅需单向遍历的场景，双向链表适用于需要双向遍历或频繁的插入和删除操作的场景，循环链表适用于需要循环遍历的场景。

3.3 链表的插入、删除和查找操作

链表的插入、删除和查找操作是常见的链表操作，它们的时间复杂度和空间复杂度如下所示：

1. 插入操作：

   • 最好情况时间复杂度：O(1)。当要插入的节点需要插入到链表的开头时，只需将节点插入并更新指针。
   • 最坏情况时间复杂度：O(n)。当要插入的节点需要插入到链表的末尾时，需要遍历整个链表找到最后一个节点，然后进行插入。
   • 平均情况时间复杂度：O(n)。平均情况下，需要遍历链表的一半来找到插入位置。

   void insertNode(Node **head, int data) {
       Node *newNode = (Node *)malloc(sizeof(Node));
       newNode->data = data;
       newNode->next = NULL;
   
       if (*head == NULL) {
           *head = newNode;
       } else {
           Node *current = *head;
           while (current->next != NULL) {
               current = current->next;
           }
           current->next = newNode;
       }
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15

2. 删除操作：

   • 最好情况时间复杂度：O(1)。当要删除的节点是链表的第一个节点时，只需更新指针。
   • 最坏情况时间复杂度：O(n)。当要删除的节点是链表的最后一个节点时，需要遍历整个链表找到该节点，并更新前一个节点的指针。
   • 平均情况时间复杂度：O(n)。平均情况下，需要遍历链表的一半来找到删除位置。

   void deleteNode(Node **head, int data) {
       if (*head == NULL) {
           return;
       }
       if ((*head)->data == data) {
           Node *temp = *head;
           *head = (*head)->next;
           free(temp);
           return;
       }
       Node *current = *head;
       Node *prev = NULL;
       while (current != NULL) {
           if (current->data == data) {
               prev->next = current->next;
               free(current);
               return;
           }
           prev = current;
           current = current->next;
       }
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22

3. 查找操作：

   • 最好情况时间复杂度：O(1)。当要查找的节点是链表的第一个节点时，直接返回该节点。
   • 最坏情况时间复杂度：O(n)。当要查找的节点位于链表的最后一个位置或不存在于链表中时，需要遍历整个链表才能找到或确定不存在。
   • 平均情况时间复杂度：O(n)。平均情况下，需要遍历链表的一半来找到目标节点。

   Node *searchNode(Node *head, int data) {
       Node *current = head;
       while (current != NULL) {
           if (current->data == data) {
               return current;
           }
           current = current->next;
       }
       return NULL;
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10

链表的空间复杂度是 O(n)，其中 n 是链表中节点的数量，因为需要存储每个节点的数据和指针。

3.4 链表的应用场景和注意事项

链表在许多场景中都有广泛的应用，以下是一些常见的应用场景和注意事项：
应用场景：

1. 实现动态数据结构：链表的动态性和灵活性使其适用于实现许多动态数据结构，如栈、队列和图等。链表可以根据需要动态地添加或删除节点，适应数据结构的变化。
2. 内存管理：链表可以用于内存管理，例如实现动态分配和释放内存的内存池。链表的插入和删除操作对于分配和释放内存块很有用，可以灵活地管理内存资源。
3. 实现缓存和缓冲区：链表可用于实现缓存和缓冲区，提供高效的数据读写和临时存储。例如，实现文件缓冲区、网络数据包缓冲区等。
4. 大数据处理：链表在大数据处理中也有应用。链表可以用于处理海量数据，通过逐个节点的处理和遍历，提供高效的数据处理和分析能力。

注意事项：

1. 内存管理：链表的动态分配和释放节点可能导致内存碎片问题，需要注意及时释放不再使用的节点，避免内存浪费。
2. 指针操作：链表的节点通过指针进行连接，需要注意指针的正确使用，避免空指针和野指针等错误。
3. 随机访问效率低：链表的访问需要从头节点开始按顺序遍历，因此随机访问效率较低。如果需要频繁的随机访问操作，可能需要考虑其他数据结构。
4. 插入和删除的效率：链表的插入和删除操作相对高效，但如果需要频繁插入和删除操作，可能存在较多的指针操作，导致性能下降。
5. 注意内存泄漏：由于链表的动态性质，容易出现内存泄漏问题。需要注意及时释放不再使用的节点，防止内存泄漏。
6. 指针引起的错误：链表的操作需要小心处理指针，避免出现指针引用错误、指针操作错误等问题，导致程序崩溃或不正确的结果。

使用链表时，需要根据具体的需求和操作特点进行选择。链表适用于动态数据结构、频繁的插入和删除操作，以及对内存占用要求较灵活的场景。但对于需要频繁随机访问和对内存占用有严格要求的场景，可能需要考虑其他数据结构的选择。

四、数组与链表的比较

4.1 内存分配和存储方式的差异

数组和链表是常见的数据结构，它们在内存分配和存储方式上有一些重要的差异。

1. 内存分配：
   • 数组：数组在静态内存分配时，需要一块连续的内存空间来存储元素。在编译时或运行时，需要提前知道数组的大小。动态分配数组时，使用malloc或new等函数来申请一块连续的内存空间。
   • 链表：链表的内存分配是动态的，每个节点可以在任何位置分配。链表节点通过指针进行连接，每个节点都需要额外的指针来存储下一个节点的地址。
2. 存储方式：
   • 数组：数组中的元素在内存中是连续存储的，通过索引可以快速访问元素。可以通过索引计算元素的内存地址，因此随机访问的时间复杂度是O(1)。
   • 链表：链表中的节点可以在内存中分散存储，每个节点存储数据和指向下一个节点的指针。链表的访问需要从头节点开始按顺序遍历，因此随机访问的时间复杂度是O(n)，其中n是节点的数量。
3. 灵活性：
   • 数组：数组在创建时需要指定大小，大小固定，不易扩展。如果需要插入或删除元素，可能需要进行元素的移动和内存重新分配。
   • 链表：链表的大小可以根据需要动态增加或减少，灵活性更强。插入或删除节点只需要调整指针的连接，不需要移动元素或重新分配内存。

4.2 插入、删除和查找操作的效率比较

在数组和链表中，插入、删除和查找操作的效率有所差异。

1. 插入操作：
   • 数组：在数组中插入元素需要将插入位置后的所有元素向后移动，以腾出位置给新的元素。这个过程的时间复杂度是O(n)，其中n是数组的大小。如果需要在数组的开头或末尾插入元素，时间复杂度为O(n)。在数组中间插入元素的平均时间复杂度为O(n/2)，即O(n)。
   • 链表：链表的插入操作相对较快。在链表中插入元素只需要调整节点的指针连接，不需要移动其他节点。无论是在链表的开头、末尾还是中间插入元素，时间复杂度都是O(1)。
2. 删除操作：
   • 数组：在数组中删除元素需要将删除位置后的所有元素向前移动，以填补删除的空缺。这个过程的时间复杂度是O(n)，其中n是数组的大小。如果需要删除数组的开头或末尾的元素，时间复杂度为O(n)。在数组中间删除元素的平均时间复杂度为O(n/2)，即O(n)。
   • 链表：链表的删除操作相对较快。在链表中删除元素只需要调整节点的指针连接，不需要移动其他节点。无论是删除链表的开头、末尾还是中间的元素，时间复杂度都是O(1)。
3. 查找操作：
   • 数组：数组具有良好的随机访问性能，可以通过索引快速定位元素。查找特定索引的元素时间复杂度是O(1)。但对于无序数组的线性查找，时间复杂度是O(n)，其中n是数组的大小。
   • 链表：链表的查找操作需要从头节点开始按顺序遍历，直到找到目标元素或遍历到链表末尾。在最坏情况下，需要遍历整个链表，时间复杂度是O(n)，其中n是链表的长度。

Tip：数组适用于需要快速随机访问的场景，而链表适用于频繁的插入和删除操作。在插入和删除操作方面，链表具有较好的性能。在查找操作方面，数组由于具有随机访问的能力，通常比链表快。根据实际需求选择合适的数据结构可以提高操作效率。

4.3 随机访问和顺序访问的优缺点

随机访问和顺序访问是两种不同的访问方式，它们在不同场景下具有各自的优点和缺点。
随机访问的优点：

1. 快速访问：通过索引或地址可以直接访问特定位置的元素，时间复杂度为O(1)。在数组等具有随机访问性质的数据结构中，随机访问速度很快。
2. 灵活性：随机访问允许按需访问数据，可以自由选择需要访问的元素，无需按照固定的顺序遍历。

随机访问的缺点：

1. 限制性：随机访问要求使用支持随机访问的数据结构，如数组。对于不支持随机访问的数据结构，如链表，无法直接进行随机访问。
2. 插入和删除的效率：在数组等支持随机访问的数据结构中，插入和删除操作可能导致元素的移动，时间复杂度为O(n)，其中n是元素的数量。因此，频繁的插入和删除操作可能影响性能。

顺序访问的优点：

1. 顺序性：顺序访问按照元素在数据结构中的顺序进行访问，适用于需要按照顺序处理数据的场景。
2. 数据预取：顺序访问可以利用预取技术，提前加载数据到缓存中，减少数据访问的延迟。

顺序访问的缺点：

1. 顺序性限制：顺序访问要求按照固定的顺序进行访问，无法随机访问特定位置的元素。
2. 难以中断和跳跃：在顺序访问过程中，中断或跳跃到其他位置可能导致重新开始或丢失之前的进度。

Tip：随机访问适用于需要快速访问特定位置的场景，而顺序访问适用于按照顺序处理数据的场景。根据实际需求选择适当的访问方式可以提高数据访问的效率和性能。

4.4 根据场景选择合适的数据结构

在选择数据结构时，应根据具体场景和需求来判断哪种数据结构更适合。以下是一些常见的场景和相应的数据结构选择：

1. 快速访问和随机访问：
   • 快速访问：如果需要频繁地通过索引或键快速访问元素，数组或哈希表是较好的选择。数组支持常数时间复杂度的随机访问，而哈希表通过键值对的映射提供快速访问。
   • 随机访问：如果需要按照任意顺序访问元素，链表可能不是最佳选择。相比之下，数组或树结构（如二叉树）更适合支持随机访问。
2. 插入和删除操作：
   • 插入和删除频繁：如果需要频繁地进行插入和删除操作，链表是一种较好的选择。链表的插入和删除操作时间复杂度为O(1)，无需移动其他元素。
   • 插入和删除固定位置：如果需要在固定位置进行插入和删除操作，而不涉及其他元素的移动，数组是更合适的选择。
3. 数据的动态性：
   • 动态大小：如果数据集合的大小需要频繁地进行动态调整，链表是一种适用的数据结构。链表的大小可以动态增加或减少，而数组的大小是固定的。
   • 固定大小：如果数据集合的大小是固定的且不需要频繁调整，数组是一种更简单且更有效的选择。
4. 数据的排序和搜索：
   • 排序：如果需要对数据进行排序操作，常用的数据结构是数组或二叉搜索树。数组可以通过排序算法进行排序，而二叉搜索树可以在插入元素时自动保持有序。
   • 搜索：如果需要根据某个键快速查找元素，哈希表或二叉搜索树是常用的数据结构。哈希表通过键值对的映射提供O(1)时间复杂度的查找，而二叉搜索树提供较快的查找速度。
5. 内存占用和性能要求：
   • 内存占用：如果对内存占用有严格要求，链表通常比数组更加灵活。链表的内存分配是动态的，可以根据需求进行灵活分配，而数组需要一块连续的内存空间。
   • 性能要求：不同数据结构在不同操作上的性能表现不同。在选择数据结构时，应考虑操作的时间复杂度和空间复杂度，以及具体场景对性能的要求。

Tip：根据具体的场景和需求，选择合适的数据结构可以提高程序的效率和性能。理解各种数据结构的特点和适用场景是合理选择的关键。

五、经典面试题与解析

5.1 逆转链表

给定一个单链表，将其逆转，即将链表的每个节点的指针方向反转。
示例：
输入: 1 -> 2 -> 3 -> 4 -> 5
输出: 5 -> 4 -> 3 -> 2 -> 1
解析：
逆转链表是一个常见的面试题，解决这个问题有多种方法。其中一种常用的方法是使用迭代法。
算法步骤：

1. 定义三个指针：prev、curr、next。初始时，prev指向NULL，curr指向链表的头节点。
2. 迭代遍历链表，每次迭代时，将curr的指针指向prev，然后依次将prev、curr、next指针向后移动一个节点。
3. 重复步骤2，直到curr指针达到链表的末尾（即curr指针为空）。
4. 最后将链表的头节点指针指向prev，完成链表的逆转。

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *prev = NULL;
    struct ListNode *curr = head;
    struct ListNode *next;

    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }

    return prev;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

上面的代码中我们使用了迭代法。通过迭代法我们可以将给定的单链表逆转。算法的时间复杂度是O(n)，其中n是链表的长度，因为需要遍历整个链表进行指针的修改。空间复杂度是O(1)，因为只需要使用常数级别的额外空间。

5.2 删除链表倒数第N个节点

给定一个单链表，删除倒数第N个节点，并返回删除后的链表。
示例：
输入: 1 -> 2 -> 3 -> 4 -> 5, N = 2
输出: 1 -> 2 -> 3 -> 5
解析：
删除链表倒数第N个节点是一个常见的面试题，解决这个问题可以使用双指针法。
算法步骤：

1. 定义两个指针：fast和slow，初始时都指向链表的头节点。
2. 将fast指针向后移动N个节点，使得fast和slow之间的距离为N。
3. 同时移动fast和slow指针，直到fast指针指向链表的末尾，即fast指针为空。
4. 此时，slow指针指向倒数第N+1个节点的前一个节点。
5. 将slow指针的next指针指向slow指针的下下个节点，即删除倒数第N个节点。

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode *dummy = malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode *fast = dummy;
    struct ListNode *slow = dummy;

    // 将fast指针向后移动N个节点
    for (int i = 0; i < n; i++) {
        fast = fast->next;
    }

    // 同时移动fast和slow指针
    while (fast->next != NULL) {
        fast = fast->next;
        slow = slow->next;
    }

    // 删除倒数第N个节点
    struct ListNode *temp = slow->next;
    slow->next = slow->next->next;
    free(temp);

    return dummy->next;
}
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

这个问题我们使用了双指针法，可以删除链表倒数第N个节点。算法的时间复杂度是O(L)，其中L是链表的长度，因为需要遍历整个链表找到倒数第N个节点。空间复杂度是O(1)，因为只需要使用常数级别的额外空间。

5.3 合并两个有序数组

给定两个有序数组nums1和nums2，将nums2合并到nums1中，并确保合并后的nums1仍然保持有序。
示例：
输入：
nums1 = [1, 2, 3, 0, 0, 0]
nums2 = [2, 5, 6]
输出：
nums1 = [1, 2, 2, 3, 5, 6]
解析：
合并两个有序数组是一个常见的面试题，可以使用双指针法解决。
算法步骤：

1. 初始化两个指针p1和p2，分别指向nums1和nums2的末尾。
2. 初始化一个指针p指向nums1的最后一个位置，即m+n-1，其中m为nums1的有效元素个数，n为nums2的有效元素个数。
3. 比较p1和p2指向的元素大小，将较大的元素复制到p指向的位置，并将对应的指针向前移动一位。
4. 重复步骤3，直到p1或p2指针到达数组的起始位置。
5. 如果nums2还有剩余的元素，将其复制到nums1的前面位置。

void merge(int* nums1, int m, int* nums2, int n) {
    int p1 = m - 1;
    int p2 = n - 1;
    int p = m + n - 1;

    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }

    while (p2 >= 0) {
        nums1[p] = nums2[p2];
        p2--;
        p--;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

这里我们同样使用了双指针法，我们可以将两个有序数组合并到nums1中，并保持nums1的有序性。算法的时间复杂度是O(m+n)，其中m为nums1的有效元素个数，n为nums2的有效元素个数。空间复杂度是O(1)，因为只需要使用常数级别的额外空间。

5.4 实现动态数组

请实现一个动态数组，支持以下操作：

1. 初始化数组：创建一个空的动态数组。
2. 添加元素：将一个元素添加到数组的末尾。
3. 获取元素：获取数组指定位置的元素值。
4. 更新元素：更新数组指定位置的元素值。
5. 删除元素：删除数组指定位置的元素。

解析：
动态数组是一种可以根据需要自动调整大小的数组结构。在许多编程语言中，可以使用动态内存分配来实现动态数组。
算法步骤：
7. 初始化数组时，分配一定大小的内存空间，并设置初始的元素个数和容量。
8. 添加元素时，检查数组容量是否足够，若不足则进行扩容，然后将新元素添加到数组的末尾。
9. 获取元素时，检查索引的有效性，若有效则返回对应位置的元素值。
10. 更新元素时，检查索引的有效性，若有效则更新对应位置的元素值。
11. 删除元素时，检查索引的有效性，若有效则将后面的元素向前移动一个位置，同时更新元素个数。
12. 若数组的元素个数小于容量的一半，并且大于某个最小容量阈值，可以考虑进行缩容操作。

#include 
#include 

typedef struct {
    int* data;       // 指向动态数组的指针
    int size;        // 数组的当前元素个数
    int capacity;    // 数组的容量
} DynamicArray;

// 初始化动态数组
void initDynamicArray(DynamicArray* arr, int capacity) {
    arr->data = (int*)malloc(capacity * sizeof(int));
    arr->size = 0;
    arr->capacity = capacity;
}

// 添加元素到数组末尾
void append(DynamicArray* arr, int value) {
    if (arr->size == arr->capacity) {
        // 当数组容量不足时，进行扩容
        arr->capacity *= 2;
        arr->data = (int*)realloc(arr->data, arr->capacity * sizeof(int));
    }

    arr->data[arr->size] = value;
    arr->size++;
}

// 获取指定位置的元素
int get(DynamicArray* arr, int index) {
    if (index >= 0 && index < arr->size) {
        return arr->data[index];
    }
    return -1;  // 返回一个无效值表示索引越界
}

// 更新指定位置的元素
void update(DynamicArray* arr, int index, int value) {
    if (index >= 0 && index < arr->size) {
        arr->data[index] = value;
    }
}

// 删除指定位置的元素
void removeElement(DynamicArray* arr, int index) {
    if (index >= 0 && index < arr->size) {
        for (int i = index; i < arr->size - 1; i++) {
            arr->

data[i] = arr->data[i + 1];
        }
        arr->size--;

        // 当数组元素个数小于容量的一半，并且大于某个最小容量阈值时，进行缩容
        if (arr->size < arr->capacity / 2 && arr->capacity > 4) {
            arr->capacity /= 2;
            arr->data = (int*)realloc(arr->data, arr->capacity * sizeof(int));
        }
    }
}

// 释放动态数组内存
void freeDynamicArray(DynamicArray* arr) {
    free(arr->data);
    arr->data = NULL;
    arr->size = 0;
    arr->capacity = 0;
}

int main() {
    DynamicArray arr;
    initDynamicArray(&arr, 4);

    append(&arr, 1);
    append(&arr, 2);
    append(&arr, 3);

    printf("Element at index 1: %d\n", get(&arr, 1));

    update(&arr, 2, 4);

    removeElement(&arr, 0);

    for (int i = 0; i < arr.size; i++) {
        printf("%d ", arr.data[i]);
    }
    printf("\n");

    freeDynamicArray(&arr);

    return 0;
}
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

上述代码中，我们使用DynamicArray结构体来表示动态数组。通过调用initDynamicArray函数进行初始化，并使用append函数在数组末尾添加元素。使用get函数获取指定位置的元素值，使用update函数更新指定位置的元素值，使用removeElement函数删除指定位置的元素。在添加和删除元素时，如果数组的元素个数小于容量的一半，并且容量大于某个最小容量阈值时，可以进行缩容操作。最后，通过调用freeDynamicArray函数释放动态数组的内存。

Tip：在实际应用中，动态数组的实现可能需要考虑更多的细节，如插入元素、动态调整缩容的阈值等。上述示例代码提供了一个基本的动态数组实现框架，您可以根据实际需求进行扩展和修改。

5.5 数组和链表的综合应用题

假设有一个名为Person的结构体，包含两个字段：姓名（name）和年龄（age）。请设计一个数据结构，能够存储一组Person对象，并支持以下操作：

1. 添加Person对象到数据结构中。
2. 根据姓名查找Person对象。
3. 根据年龄删除Person对象。
4. 获取数据结构中Person对象的数量。

解析：
为了实现上述功能，可以结合数组和链表的特点进行设计。使用数组来存储Person对象的指针，方便根据索引进行访问。同时，使用链表来连接数组中的Person对象，方便根据姓名进行查找和根据年龄进行删除。
具体实现步骤：

1. 定义Person结构体，包含name和age字段。
2. 定义Node结构体，包含指向Person对象的指针和指向下一个Node的指针。
3. 定义数据结构，包含数组和链表的相关信息，如数组的容量、当前元素个数以及链表的头指针。
4. 添加Person对象时，先创建一个新的Person对象，并将其指针添加到数组中。然后，创建一个对应的Node对象，并将其插入链表的头部。
5. 根据姓名查找Person对象时，从链表头开始遍历，比较每个Node中的Person对象的姓名，直到找到匹配的姓名或遍历结束。
6. 根据年龄删除Person对象时，从链表头开始遍历，找到第一个匹配年龄的Node，并将其从链表中删除。同时，需要在数组中释放对应的Person对象的内存。
7. 获取Person对象的数量时，直接返回数组中的元素个数。

下面是一个简化的C语言代码示例，演示了如何实现上述功能：

#include 
#include 
#include 

typedef struct {
    char name[20];
    int age;
} Person;

typedef struct Node {
    Person* person;
    struct Node* next;
} Node;

typedef struct {
    Person** array;
    Node* head;
    int capacity;
    int count;
} DataStructure;

void init(DataStructure* ds, int capacity) {
    ds->array = (Person**)malloc(capacity * sizeof(Person*));
    ds->head = NULL;
    ds->capacity = capacity;
    ds->count = 0;
}

void addPerson(DataStructure* ds, Person* person) {
    if (ds->count == ds->capacity) {
        // 数组已满，进行扩容
        ds->capacity *= 2;
        ds->array = (Person**)realloc(ds->array, ds->capacity * sizeof(Person*));
    }

    // 将Person指针添加到数组中
    ds->array[ds->count] = person;
    ds->count++;

    // 创建新的Node并插入链表头部
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->person = person;
    newNode->next = ds->head;
    ds-> head = newNode;
}

Person* findPerson(DataStructure* ds, const char* name) {
    Node* current = ds->head;
    while (current != NULL) {
        if (strcmp(current->person->name, name) == 0) {
            return current->person;
        }
        current = current->next;
    }
    return NULL;
}

void removePerson(DataStructure* ds, int age) {
    Node* prev = NULL;
    Node* current = ds->head;

    while (current != NULL) {
        if (current->person->age == age) {
            // 从数组中释放Person对象的内存
            for (int i = 0; i < ds->count; i++) {
                if (ds->array[i] == current->person) {
                    free(ds->array[i]);
                    ds->array[i] = NULL;
                    break;
                }
            }

            if (prev == NULL) {
                // 删除头节点
                ds->head = current->next;
            } else {
                // 删除中间或尾节点
                prev->next = current->next;
            }

            free(current);
            current = NULL;
            ds->count--;
            break;
        }

        prev = current;
        current = current->next;
    }
}

int getPersonCount(DataStructure* ds) {
    return ds->count;
}

void freeDataStructure(DataStructure* ds) {
    // 释放链表节点的内存
    Node* current = ds->head;
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }

    // 释放数组中Person对象的内存
    for (int i = 0; i < ds->count; i++) {
        free(ds->array[i]);
    }

    // 释放数组和数据结构对象的内存
    free(ds->array);
    ds->array = NULL;
    ds->head = NULL;
    ds->capacity = 0;
    ds->count = 0;
}

int main() {
    DataStructure ds;
    init(&ds, 5);

    // 添加Person对象
    Person* person1 = (Person*)malloc(sizeof(Person));
    strcpy(person1->name, "Alice");
    person1->age = 25;
    addPerson(&ds, person1);

    Person* person2 = (Person*)malloc(sizeof(Person));
    strcpy(person2->name, "Bob");
    person2->age = 30;
    addPerson(&ds, person2);

    // 查找Person对象
    Person* result = findPerson(&ds, "Alice");
    if (result != NULL) {
        printf("Person found: %s, age: %d\n", result->name, result->age);
    } else {
        printf("Person not found\n");
    }

    // 删除Person对象
    removePerson(&ds, 30);

    // 获取Person对象数量
    int count = getPersonCount(&ds);
    printf("Person count: %d\n", count);

    // 释放数据结构内存
    freeDataStructure(&ds);

    return 0;
}
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

上述代码中，我们定义了Person结构体来表示每个Person对象，定义了Node结构体作为链表的节点，定义了DataStructure结构体作为整个数据结构的信息。通过调用init函数进行初始化，使用addPerson函数向数据结构中添加Person对象，使用findPerson函数根据姓名查找Person对象，使用removePerson函数根据年龄删除Person对象，使用getPersonCount函数获取Person对象的数量。最后，通过调用freeDataStructure函数释放数据结构的内存。
这个综合应用题结合了数组和链表的特点，可以实现对一组Person对象的灵活管理。请注意，上述示例代码提供了一个基本的实现框架，您可以根据实际需求进行扩展和修改。

六、总结

数组和链表是常见的数据结构，在实际应用中具有不同的优缺点，根据需求选择合适的数据结构对程序的性能和效率至关重要。
数组的优缺点：

链表的优缺点：

根据需求选择合适的数据结构的原则：

1. 如果需要频繁的随机访问或固定大小的集合，使用数组更合适。
2. 如果需要频繁的插入和删除操作或动态大小的集合，使用链表更合适。
3. 如果需要兼顾随机访问和插入/删除操作，可以考虑其他数据结构，如树或哈希表。