🏷️ 知识点：链表

已知表头元素为 c 的单链表在内存中的存储状态如下表所示。现将 f 存放于 1014H 处并插入单链表，若 f 在逻辑上位于 a 和 e 之间，则 a,e,f 的 “链接地址” 依次是（ ）。

链表

A. 1010H，1014H，1004H B. 1010H，1004H，1014H C. 1014H，1010H，1004H D. 1014H，1004H，1010H

[tag_link]

正确答案：D

根据存储状态，单链表的结构如下图所示。其中“链接地址”是指结点 next 所指的内存地址。当结点 f 插入后，a 指向 f, f 指向 e, e 指向 b。显然 a、e 和 f 的“链接地址”分别是 f、b 和 e 的内存地址，即 1014H、1004H 和 1010H。

已知头指针 h 指向一个带头结点的非空单循环链表，结点结构为

其中 next 是指向直接后继结点的指针，p 是尾指针，q 是临时指针。现要删除该链表的第一个元素，正确的语句序列是（ ）。

链表

A. h->next = h->next->next; q = h->next; free(q); B. q = h->next; h->next = h->next->next; free(q); C. q = h->next; h->next = q->next; if (p != q) p = h; free(q); D. q = h->next; h->next = q->next; if (p == q) p = h; free(q);

[tag_link]

正确答案：D

删除 头结点后一个结点的基本流程为q = h->next; h->next = q->next; free(q);，即通过指针操作跳过下一个结点后删除该结点。 由于题目中提到了该链表非空，所以可以确定q = h->next一定不为空。 但是如果链表中只有一个结点的话，我们还需要在删除该结点后，将尾指针指向头结点的位置，即if (p == q) p = h;

已知带头结点的非空单链表 L 的头指针为 h，指针 p 指向 L 中间的一个链表结点（不是第一个和最后一个结点）。q=p->next，p->next=q->next，q->next=h->next，h->next=q。这段代码的功能是（）。

链表

A. 把 q 指向的结点插入到 p 的后面 B. 把 p 指向的结点插入到 q 的后面 C. 把 p 指向的结点插入到 h 的后面 D. 把 q 指向的结点插入到 h 的后面

[tag_link]

正确答案：D

代码分解分析：

q = p->next;

现在 q 指向的是 p 的下一个结点。

p->next = q->next;

这一步将 q 从链表中“摘除”：原本是 p -> q -> q->next，现在变成了 p -> q->next，也就是说 q 不再出现在链表的原位置。

q->next = h->next;

这一步将 q->next 指向当前链表的第一个有效结点（注意是 h->next，即第一个结点，不是头结点）。

h->next = q;

把 q 接到头结点之后，也就是插入到链表头部（第一个有效结点之前）。操作的效果是：从链表中间删除了 q，然后把它插入到了头结点之后，也就是插入到链表第一个有效结点之前。所以这段代码的功能是：

把 q 指向的结点插入到 h 的后面 [tag_link]

正确答案选择 D。

用链表方式存储的队列（有头尾指针非循环），在进行删除运算时（ ）。

A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改

队列 链表

[tag_link]

正确答案：D

在链表方式存储的队列中，头指针指向队头节点，尾指针指向队尾节点，且为非循环链表。 进行删除运算时，通常从队头删除节点。

如果队列中有多个节点，删除队头节点后，只需修改头指针指向下一个节点，尾指针保持不变，因为队尾节点未变。 如果队列中只有一个节点，删除后队列为空，此时需要将头指针和尾指针都修改为 NULL，表示队列为空。

因此，删除操作中头指针总是需要修改，而尾指针仅在队列变空时需要修改，否则不变。 这意味着头、尾指针可能都要修改，也可能只修改头指针，故选项 D 正确。

已知一个带有表头结点的双向循环链表 L，结点结构为 prev|data|next，prev 和 next 分别是指向其直接前驱和直接后继结点的指针。现要删除指针 p 所指的结点，正确的语句序列是（ ）。

链表

A. p->next->prev = p->prev; p->prev->next = p->prev; free(p); B. p->next->prev = p->next; p->prev->next = p->next; free(p); C. p->next->prev = p->next; p-> prev->next = p->prev; free(p); D. p->next->prev = p->prev; p->prev->next = p->next; free(p);

[tag_link]

正确答案：D

参考 单链表删除 操作，这种题为送分题。

现有非空双向链表 L，其结点结构为：

prev 是指向前直接前驱结点的指针，next 是指向直接后继结点的指针。若要在 L 中指针 p 所指向的结点（非尾结点）之后插入指针 s 指向的新结点，则在执行了语句序列： s->next=p->next; p->next=s，后，还要执行（ ）。

链表

A. s->next->prev=p; s->prev=p; B. p->next->prev=s; s->prev=p; C. s->prev=s->next->prev; s->next->prev=s; D. p->next->prev=s->prev; s->next->prev=p;

[tag_link]

正确答案：C

主要考察双链表的插入操作，解决这类问题可在纸上画出具体的双链表进行模拟。因为s->next已经赋值为p的后一个结点，同时p->next指针已经赋值为s。所以只需要处理s->next->prev和s->next->prev的赋值，s->prev需要指向p，s-next->prev需要指向s。因为p->next和s指向同一个结点，所以可以用p->next代表s。故本题的正确选项为 C。

[tag_link]

用单链表保存m个整数，结点的结构为，且∣data∣≤n（n为正整数）。现要求设计一个时间复杂度尽可能高效的算法，对于链表中 data 的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表 head 如下：

则删除结点后的 head 为：

要求：

(1) 给出算法的基本设计思想。

(2) 使用 C 或 C++ 语言，给出单链表结点的数据类型定义。

(3) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

(4) 说明你所设计算法的时间复杂度和空间复杂度。

链表

1）算法的基本设计思想算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的数值，从而只需对链表进行一趟扫描。因为∣data∣≤n，故辅助数组q的大小为n+1，各元素的初值均为 0。依次扫描链表中的各结点，同时检查q[∣data∣]的值，如果为0，则保留该结点，并令q[data]=1；否则，将该结点从链表中删除。

2）使用 C 语言描述的单链表结点的数据结构定义：

3）算法实现

void RemoveElements(ListNode *head, int n) {
  // 数组充当哈希表
  int hash[n+1];
  for (int i = 0; i <= n; i++) {
    // 0 表示没有命中
    hash[i] = 0;
  }
  // 当遍历的结点
  ListNode *q = head->link;
  // 先前的结点
  ListNode *p = head;
  while (q != NULL) {
    // 绝对值已经出现过
    if (hash[abs(q->data)] == 1) {
      // 删除该节点
      p->next = q->next;
      q = p->next;
    } else {
      // 设置哈希表
      hash[abs(q->data)] = 1;
      q = q->next;
      p = p->next;
    }
  }
}

【评分说明】若考生设计的算法满足题目的功能要求且正确，则酌情给分。

4）参考答案所给算法的时间复杂度为 O(m)，空间复杂度为 O(n)。【评分说明】若考生所估计的时间复杂度和空间复杂度与考生实现的算法一致，可给分。

设线性表L=(a1 ,a2 ,a3 ,⋯,an−1 ,an−1 ,an )采用带头结点的单链表保存，链表中的结点定义如下：

typedef struct node {
    int data;
    struct node *next;
} NODE;

请设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L′=(a1 ,an ,a2 ,an−1 ,a3 ,an−2 ,⋯)。要求：

(1) 给出算法的基本设计思想。

(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

(3) 说明你所设计算法的时间复杂度。

链表

[tag_link]

1）算法的基本设计思想：先观察 L(a1 ,a2 ,a3 ,⋯,an−2 ,an−1 ,an) 和 L’(a1 ,an ,a2 ,an−1 ,a3 ,an−2 ,⋯)，发现 L’ 是由 L 摘取第一个元素，再摘取倒数第一个元素⋯依次合并而成的。为了方便链表后半段取元素，需要先将 L 后半段原地逆置［题目要求空间复杂度为 助栈］，否则每取最后一个结点都需要遍历一次链表。①先找出链表 L 的中间结点，为此设置两个指针 p 和 q，指针 p 每次走一步，指针 q 每次走两步，当指针 q 到达链尾时，指针 p 正好在链表的中间结点；②然后将 L 的后半段结点原地逆置。③从单链表前后两段中依次各取一个结点，按要求重排。

2）算法实现如下：

// 找到链表的中间结点
NODE *findMiddleNode(NODE *head) {
  NODE *slow = head;
  NODE *fast = head;
  while (fast != NULL) {
    fast = fast->next;
    if (fast != NULL) {
      fast = fast->next;
    }
    slow = slow->next;
  }
  return slow;
}

// 反转链表
NODE *reverse(NODE *start) {
  NODE *p = start;
  NODE *q = start->next;
  while (q != NULL) {
    NODE *tmp = q->next;
    q->next = p;
    p = q;
    q = tmp;
  }
  return p;
}

// 1. 找到中位结点
// 2. 翻转后一半链表
// 3. 遍历两个链表，依次穿插所有结点
void solve(HEAD *head) {
  if (head->next == NULL) {
    return;
  }
  NODE *middle = findMiddleNode(head);
  NODE *list2 = reverse(middle);
  NODE *list1 = head->next;
  // 穿插操作
  NODE *p = list1;
  NODE *q = list2;
  // 退出循环的条件
  // 链表长度为奇数：p == q
  // 链表长度为偶数：p->next == q
  // while (!(p == q || p->next == q))
  while (p != q && p->next != q) {
    NODE *tmp1 = p->next;
    NODE *tmp2 = q->next;
    p->next = q;
    q->next = tmp1;
    p = tmp1;
    q = tmp2;
  }
}

3）第 1 步找中间结点的时间复杂度为 O(n)，第 2 步逆置的时间复杂度为 O(n)，第 3 步合并链表的时间复杂度为 O(n)，所以该算法的时间复杂度为 O(n)。

（12 分）假设二叉树采用二叉链表存储结构，设计一个算法求其指定的某一层 k （ k > 1 ）的叶子结点个数，要求：

（1）给出算法的基本设计思想。

（2）写出二叉树采用的存储结构代码。

（3）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

复杂度分析 链表

[tag_link]

【答案】

（1）算法的基本设计思想：采用递归先序遍历二叉树，遍历时记录当前节点所在层数。若当前层数等于指定层数 k ，则判断该节点是否为叶子结点（左右孩子均为空），若是则计数器加 1；若当前层数小于 k ，则递归遍历其左右子树；若当前层数大于 k ，则停止向下递归。最终累计得到第 k 层的叶子结点个数。

（2）二叉树采用的二叉链表存储结构代码： typedef struct BiTNode { char data ; // 结点数据，假设为字符型 struct BiTNode * lchild , * rchild ; // 左右孩子指针 } BiTNode , * BiTree ;

（3）算法描述（C 语言）： // 函数功能：计算二叉树 T 中第 k 层的叶子结点个数 // 参数：T 为二叉树根结点指针，currentLevel 为当前结点所在层数（根结点为第 1 层），k 为指定层数 // 返回值：第 k 层的叶子结点个数 int countLeafAtLevel ( BiTree T , int currentLevel , int k ) { if ( T == NULL ) { // 空树，返回 0 return 0 ; } if ( currentLevel == k ) { // 到达第 k 层 // 判断是否为叶子结点 if ( T -> lchild == NULL && T -> rchild == NULL ) { return 1 ; } else { return 0 ; } } else if ( currentLevel < k ) { // 当前层小于 k，继续向下递归 return countLeafAtLevel ( T -> lchild , currentLevel + 1 , k ) + countLeafAtLevel ( T -> rchild , currentLevel + 1 , k ); } else { // 当前层大于 k，不再递归 return 0 ; } } // 调用示例：int leafCount = countLeafAtLevel(root, 1, k); 【解析】 算法设计思想解析：由于需要统计二叉树中指定层 k 的叶子结点个数，采用深度优先搜索（DFS）策略，通过递归遍历二叉树并在过程中跟踪当前层数。当层数等于 k 时，判断当前结点是否为叶子结点并进行计数；若层数小于 k ，则继续递归遍历左右子树；若层数大于 k ，则提前返回，避免无效访问。这种方法只需遍历一次二叉树，且在层数超过 k 时停止递归，提高了效率。 存储结构采用标准的二叉链表，每个结点包含数据域和指向左右子树的指针，便于递归操作。 算法实现时，递归终止条件包括：结点为空时返回 0；当前层数等于 k 时，根据叶子结点定义返回 1 或 0；当前层数小于 k 时，递归计算左右子树的叶子结点数之和；当前层数大于 k 时直接返回 0。该算法的时间复杂度为 O ( n ) ，最坏情况下需访问所有结点（当 k 大于等于树高时）；空间复杂度为 O ( h ) ， h 为树的高度，即递归栈的深度。注意题目中 k > 1 ，但算法对 k = 1 同样适用，调用时传入 currentLevel=1 即可。

单链表有环，是指单链表的最后一个结点的指针指向了链表中的某个结点（通常单链表的最后一个结点的指针域是为空的）。试编写算法判断单链表是否存在环。

（1）给出算法的基本设计思想。

（2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。

链表 复杂度分析

[tag_link]

【答案】

（1）基本设计思想：采用快慢指针法（Floyd 判圈算法）。设置两个指针，慢指针每次移动一步，快指针每次移动两步。如果链表中存在环，快指针最终会追上慢指针并相遇；如果不存在环，快指针会首先到达链表尾部（即指向 NULL）。

（2）算法描述（C++）： struct ListNode { int val ; ListNode * next ; ListNode ( int x ) : val ( x ), next ( NULL ) {} }; bool hasCycle ( ListNode * head ) { if ( head == NULL || head -> next == NULL ) { return false ; // 空链表或只有一个节点且无环 } ListNode * slow = head ; ListNode * fast = head ; while ( fast != NULL && fast -> next != NULL ) { slow = slow -> next ; // 慢指针移动一步 fast = fast -> next -> next ; // 快指针移动两步 if ( slow == fast ) { return true ; // 相遇，说明有环 } } return false ; // 快指针到达尾部，说明无环 }

（3）时间复杂度：O(n)，其中 n 为链表节点数。在最坏情况下，需要遍历整个链表一次或两次。空间复杂度：O(1)，仅使用了两个额外指针。 【解析】 该算法的核心是快慢指针的追逐原理。如果链表有环，快指针每次比慢指针多移动一步，两者在环内的相对距离每次减少一步，因此必然会在有限步内相遇；如果链表无环，快指针将先到达链表尾部（即遇到 NULL）。时间复杂度为 O(n)，因为每个节点最多被访问两次（快指针可能遍历两次）；空间复杂度为 O(1)，因为只使用了常数级别的额外空间。这种方法是判断链表是否存在环的最优解之一，既高效又节省内存。

假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading" 和 “being” 的存储映像如下图所示。

设 str1 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为 | data | next |，请设计一个时间上尽可能高效的算法，找出由 str1 和 str2 所指向两个链表共同后缀的起始位置（如图中字符 i 所在的结点位置 p）。要求：

1）给出算法的基本设计思想。

2）根据设计思想，采用 C 或 C++ 或 Java 语言描述算法，关键之处给出注释。

3）说明你所设计算法的时间复杂度。

链表

[tag_link]

顺序遍历两个链表到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另 一个链表长 k 个结点，我们先在长链表上遍历 k 个结点，之后同步遍历两个链表，这样就能够保证它们同时到达最后一个结点。由于两个链表从第一个公共结点到链表的尾结点都是重合的，所以它们肯定同时到达第 一个公共结点。算法的基本设计思想：①分别求出 strl 和 str2 所指的两个链表的长度 m 和 n。②将两个链表以表尾对齐：令指针 p、q 分别指向 strl 和 str2 的头结点，若m≥n，则使 p 指向链表中的第 m-n+1 个结点；若m<n，则使 q 指向链表中的第 n-m+1 个结点，即使指针 p 和 q 所指的结点到表尾的长度相等。③反复将指针 p 和 q 同步向后移动，并判断它们是否指向同一结点。若 p 和 q 指向同一结点，则该点即为所求的共同后缀的起始位置。

2）算法的 C 语言代码描述：

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

int getLength(Node *h) {
  int length = 0;
  Node *p = h->next;
  while (p) {
    length++;
    p = p->next;
  }
  return length;
}

Node *findCommonSuffix(Node *h1, Node *h2) {
  Node *p1 = h1;
  Node *p2 = h2;
  int m = getLength(h1);
  int n = getLength(h2);
  if (m > n) {
    for (int i = 0; i < m-n; i++) {
      p1 = p1->next;
    }
  } else {
    for (int i = 0; i < n-m; i++) {
      p2 = p2->next;
    }
  }
  while (p1 != p2) {
    p1 = p1->next;
    p2 = p2->next;
  }
  return p1;
}

【评分说明】 ① 若考生所给算法实现正确，且时间复杂度为 O(m+n)，可给 12分；若算法正确，但时间复杂度超过 O(m+n)，则最高可给 9 分。② 若在算法的基本设计思想描述中因文字表达没有非常清晰反映出算法思路，但在算法实现中能够清晰看出算法思想且正确的，可参照①的标准给分。③ 若算法的基本设计思想描述或算法实现中部分正确，可参照①中各种情况的相应给分标准酌情给分。③ 时间复杂度为 O(len1+len2）或 O(max(len1,len2)), 其中 len1、len2 分别为两个链表的长度。