数据结构之线性表（2）

选择题

01. 关于线性表的顺序存储结构和链式存储结构的描述中，正确的是()。

I.线性表的顺序存储结构优于其链式存储结构

II.链式存储结构比顺序存储结构能更方便地表示各种逻辑结构

III.若频繁使用插入和删除结点操作，则顺序存储结构更优于链式存储结构

IV.顺序存储结构和链式存储结构都可以进行顺序存取

解析：

  • I 错误：两种存储结构各有适用场合，不能简单比较优劣。
  • II 正确：链式存储结构能够更方便地表示各种逻辑结构。
  • III 错误：顺序存储结构在频繁插入和删除时效率低下，因为需要移动大量元素。
  • IV 正确：顺序存储结构支持随机存取和顺序存取。

02. 对于一个线性表，既要求能够进行较快速地插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用()。

  • A. 顺序存储方式
  • B. 链式存储方式
  • C. 散列存储方式
  • D. 以上均可以
  • 答案：B

解析：

  • 链式存储方式能够方便地表示逻辑关系，并且插入和删除的时间复杂度为 $ O(1) $。

03. 对于顺序存储的线性表，其算法时间复杂度为 $ O(1) $ 的运算应该是()。

  • A. 将n个元素从小到大排序
  • B. 删除第i个元素
  • C. 改变第i个元素
  • D. 在第i个元素后插入一个新元素
  • 答案：C

解析：

  • 选项A的时间复杂度至少为 $ O(n \log n) $。
  • 选项B和D也需要移动元素，因此时间复杂度为 $ O(n) $。

04. 下列关于线性表说法中，正确的是()。

  • A. 顺序存储方式只能用于存储线性结构
  • B. 取线性表的第i个元素的时间与i的大小有关
  • C. 静态链表需要分配较大的连续空间，插入和删除不需要移动元素
  • D. 在一个长度为n的有序单链表中插入一个新结点并仍保持有序的时间复杂度为 $ O(n) $
  • E. 若用单链表来表示队列，则应该选用带尾指针的循环链表

解析：

  • A错误：顺序存储方式也适用于图和树。
  • B错误：取线性表的第i个元素的时间复杂度为 $ O(1) $。
  • C正确：静态链表不需要大块连续空间，但插入和删除仍需调整指针。
  • D正确：在有序单链表中，插入新节点的时间复杂度确实为 $ O(n) $。
  • E正确：使用带尾指针的循环链表更方便实现队列，插入和删除的复杂度都是$O(1)$。

05. 线性表中有 2n 个元素，在单链表上实现要比在顺序表上实现效率更高，正确的是()。

  • A. 删除所有值为x的元素
  • B. 在最后一个元素的后面插入一个新元素
  • C. 顺序输出前k个元素
  • D. 交换第i个元素和第 2n-i-1个元素的值(i=0…，n-1)
  • 答案：A

解析：

  • A选项在单链表上实现不需要移动元素，因此效率更高。
  • B和C在顺序表中效率更高。
  • D需要访问和交换元素，顺序表的实现更优。

06. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入结点s，则执行()。

  • A. $ s->next = p->next; p->next = s; $
  • B. $ p->next = s->next; s->next = p; $
  • C. $ q->next = s; s->next = p; $
  • D. $ p->next = s; s->next = q; $
  • 答案：C

解析：

  • 当在结点q和结点p之间插入结点s时，q的next指向s，s的next指向p，形成了新的连接。因此，选项C是正确的。

07. 给定有n个元素的一维数组，建立一个有序单链表的最低时间复杂度是()。

  • A. $ O(1) $
  • B. $ O(n) $
  • C. $ O(n^2) $
  • D. $ O(n \log n) $
  • 答案：D

解析：

  • 若先建立链表，然后依次插入元素以建立有序表，每次插入一个元素都需遍历链表寻找插入位置，因此时间复杂度为 $ O(n) $，总的时间复杂度为 $ O(n^2) $。如果是先将数组排序再建立链表，时间复杂度为 $ O(n \log n) $（排序）加上 $ O(n) $（链表构建），所以总时间复杂度为 $ O(n \log n) $。

08. 将长度为 n 的单链表链接在长度为 m 的单链表后面，其算法的时间复杂度采用大 O 形式表示应该是( )。

  • A. $ O(1) $
  • B. $ O(n) $
  • C. $ O(m) $
  • D. $ O(n + m) $
  • 答案：C

解析：

  • 为了将长度为 n 的单链表连接到长度为 m 的单链表后面，首先需要遍历长度为 m 的单链表找到尾结点，其时间复杂度为 $ O(m) $。

09. 单链表中，增加一个头结点的目的是()。

  • A. $ O(1) $
  • B. 标识表结点中首结点的位置
  • C. 方便运算的实现
  • D. 说明单链表是线性表的链式存储
  • 答案：C

解析：

  • 设置头结点的主要目的是为了方便运算的实现。通过引入头结点，可以统一处理链表的插入和删除操作，不论链表是否为空，头指针始终指向头结点，简化了对链表操作的逻辑。

10. 在一个长度为 n 的带头结点的单链表 h 上，设有尾指针 r，则执行( )操作与链表的表长有关。

  • A. 删除单链表中的第一个元素
  • B. 删除单链表中的最后一个元素
  • C. 在单链表第一个元素前插入一个新元素
  • D. 在单链表最后一个元素后插入一个新元素
  • 答案：B

解析：

  • 删除单链表的最后一个结点需要找到其前驱结点，并将其指针域置为 NULL。这需要从头结点开始遍历链表，时间复杂度为 $ O(n) $，因此该操作与链表的表长有关。其他操作（如删除第一个元素、在第一个元素前插入新元素或在最后一个元素后插入新元素）都是常数时间操作。

11. 对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是( );对于不带头结点的单链表，判定空表的条件为()。

  • A. $ head == NULL $
  • B. $ head->next == NULL $
  • C. $ head->next == head $
  • D. $ head != NULL $
  • 答案：B，A

解析：

  • 在带头结点的单链表中，头指针指向头结点，而头结点的next域指向第一个元素。如果 $ head->next == NULL $，则表示该单链表为空。
  • 在不带头结点的单链表中，如果 $ head == NULL $，则表示该单链表为空。

12. 下面关于线性表的一些说法中，正确的是()。

  • A. 对一个设有头指针和尾指针的单链表执行删除最后一个元素的操作与链表长度无关
  • B. 线性表中每个元素都有一个直接前驱和一个直接后继
  • C. 为了方便插入和删除数据，可以使用双链表存放数据
  • D. 取线性表第 i 个元素的时间与 i 的大小有关
  • 答案：C

解析：

  • 选项A是错误的，因为删除最后一个元素需要找到其前驱结点，时间复杂度与链表长度有关。
  • 选项B也是错误的，因为线性表的第一个元素没有前驱，最后一个元素没有后继。
  • 选项C是正确的，双链表可以方便地访问前驱和后继，适合插入和删除操作。
  • 选项D不正确，因为在顺序存储情况下取第 i 个元素的时间是 $ O(1) $，而在链式存储情况下，取第 i 个元素的时间复杂度为 $ O(i) $，与 i 的大小有关，但并不适用于所有情况。

13. 在双链表中向 p 所指的结点之前插入一个结点 q 的操作为()。

  • A. $ p->prior = q; q->next = p; p->prior->next = q; q->prior = p->prior; $
  • B. $ q->prior = p->prior; p->prior->next = q; q->next = p; p->prior = q; $
  • C. $ q->next = p; p->next = q; q->prior->next = q; q->next = p; $
  • D. $ p->prior->next=q;q->next=p;q->prior=p->prior;p->prior=q $
  • 答案：B,D

解析：

  • 在双链表中向p之前插入q时，首先需要设置q的前驱指针指向p的前驱结点，然后将p的前驱结点的next指针指向q，接着将q的next指针指向p，最后将p的前驱指针指向q。选项B,D正确,满足这个条件。

14. 在双向链表存储结构中，删除 p 所指的结点时必须修改指针()。

  • A. $ p->llink->rlink = p->rlink; p->rlink->llink = p->llink; $
  • B. $ p->llink = p->llink->llink; p->llink->rlink = p; $
  • C. $ p->rlink->llink = p; p->rlink = p->rlink->rlink; $
  • D. $ p->rlink = p->llink->llink; p->llink = p->rlink->rlink; $
  • 答案：A

解析：

  • 删除p所指的结点时，需要将p的前驱结点的右链指向p的后继结点，同时将p的后继结点的左链指向p的前驱结点，以保持双向链表的连接完整。选项A正确地描述了这个过程。

15. 在长度为 n 的有序单链表中插入一个新结点，并仍然保持有序的时间复杂度是( )。

  • A. $ O(1) $
  • B. $ O(n) $
  • C. $ O(m) $
  • D. $ O(n \log n) $
  • 答案：B

解析：

  • 在有序单链表中插入新结点，首先需要找到合适的位置，这个过程需要遍历链表，时间复杂度为 $ O(n) $。插入操作本身是常数时间操作，时间复杂度为 $ O(1) $。因此，总的时间复杂度为 $ O(n) $。

16. 与单链表相比，双链表的优点之一是()。

  • A. 插入、删除操作更方便
  • B. 可以进行随机访问
  • C. 可以省略表头指针或表尾指针
  • D. 访问前后相邻结点更灵活
  • 答案：D

解析：

  • 双链表在每个结点中都有前驱和后继指针，因此可以方便地访问相邻结点，特别是在进行插入和删除操作时，能够更灵活地修改指针。选项A并不完全正确，因为双链表在指针的修改上更复杂；选项B是错误的，因为双链表仍然不支持随机访问；选项C不成立，因为双链表同样需要表头或表尾指针。

17. 带头结点的双循环链表为空的条件是()。

  • A. $ L->prior == L$ && $L->next == NULL $
  • B. $ L->prior == NULL$ &&$ L->next == NULL $
  • C. $ L->prior == NULL$ &&$L->next = L $
  • D. $ L->prior = L $&& $L->next == L $
  • 答案：D

解析：

  • 在双循环链表中，头结点的前驱指针和后继指针都指向自身（即头结点自己），因此在判断空链表时，条件应为 $ L->prior == L $ 且 $ L->next == L $。选项D正确地描述了这个条件。

18. 一个链表最常用的操作是在末尾插入结点和删除结点，则选用()最节省时间。

  • A. 带头结点的双循环链表
  • B. 单循环链表
  • C. 带尾指针的单循环链表
  • D. 单链表
  • 答案：C

解析：

  • 带尾指针的单循环链表在末尾插入和删除结点时，不需要遍历整个链表来找到尾结点及其前驱结点，因此时间复杂度为 $ O(1) $。其他选项（如单链表和单循环链表）在末尾插入和删除时都需要先找到尾结点，时间复杂度为 $ O(n) $。

19. 设对 $ n (n > 1) $ 个元素的线性表的运算只有4种: 删除第一个元素; 删除最后一个元素; 在第一个元素之前插入新元素; 在最后一个元素之后插入新元素，则最好使用()。

  • A. 只有尾结点指针没有头结点指针的循环单链表
  • B. 只有尾结点指针没有头结点指针的非循环双链表
  • C. 只有头结点指针没有尾结点指针的循环双链表
  • D. 既有头结点指针又有尾结点指针的循环单链表
  • 答案：C

解析：

  • 使用循环双链表，能够方便地在头部和尾部进行插入和删除操作。由于有前驱和后继指针，可以直接访问第一个和最后一个元素，同时插入和删除的时间复杂度均为 $ O(1) $。

20. 一个链表最常用的操作是在最后一个元素后插入一个元素和删除第一个元素，则选用()最节省时间。

  • A. 不带头结点的单循环链表
  • B. 双链表
  • C. 不带头结点且有尾指针的单循环链表
  • D. 单链表
  • 答案：C

解析：

  • 不带头结点且有尾指针的单循环链表允许在尾部插入元素时直接访问尾结点，因此时间复杂度为 $ O(1) $。删除第一个元素也很高效，时间复杂度为 $ O(1) $，因此选项C是最优解。

21. 静态链表中指针表示的是()。

  • A. 下一元素的地址
  • B. 内存储器地址
  • C. 下一个元素在数组中的位置
  • D. 左链或右链指向的元素的地址
  • 答案：C

解析：

  • 静态链表中的指针称为游标，表示下一个元素在数组中的位置，而不是直接指向内存地址。

22. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构为()。

  • A. 单链表
  • B. 静态链表
  • C. 顺序表
  • D. 双链表
  • 答案：B

解析：

  • 静态链表使用数组表示，插入和删除操作不需要移动其他元素，因此适合分配较大空间并实现高效操作。

23. 某线性表用带头结点的循环单链表存储，头指针为 head，当 $ head->next->next = head $ 成立时，线性表长度可能是()。

  • A. 0
  • B. 1
  • C. 2
  • D. 可能为0或1
  • 答案：D

解析：

  • 如果链表为空，$ head->next $ 指向自身，条件成立；如果链表中有一个元素，$ head->next $ 指向该元素，该元素的下一个指针指向头结点，因此也符合条件。故选D。

24. 【2016 统考真题】已知一个带有表头结点的双向循环链表，结点结构为 $ |prev|data|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->prev->next = p->prev; free(p); p->next->prev = p->next; $
  • D. $ p->next->prev = p->prev; p->prev->next = p->next; free(p); $
  • 答案：D

解析：

  • 删除双向链表中的结点需要正确调整前驱和后继结点的指针。选项D正确地将指针链接更新为前驱和后继结点，确保链表的完整性，并最终释放结点。

25. 【2016 统考真题】已知表头元素为c的单链表在内存中的存储状态如下表所示。

地址 元素 链接地址
1000H a 1010H
1004H b 100CH
1008H c 1000H
100CH d NULL
1010H e 1004H
1014H -

现将f存放于1014H处并插入单链表，若f在逻辑上位于a和e之间，则a、e、f的“链接地址”依次是()。

  • A. 1010H, 1014H, 1004H
  • B. 1010H, 1004H, 1014H
  • C. 1014H, 1010H, 1004H
  • D. 1014H, 1004H, 1010H
  • 答案：D

image-20241006142221437

解析：

  • 根据给定的链表结构，插入f后，a的链接地址指向f（1014H），f的链接地址指向e（1004H），而e的链接地址指向b（1000H）。因此，a、e、f的“链接地址”依次是：1014H（f）、1004H（e）、1010H（b）。

26. 【2021统考真题】已知头指针h指向一个带头结点的非空单循环链表，结点结构为 $ data_next $，其中 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; \text{if}(p != q) p = h; free(q); $
  • D. $ q=h->next; h->next=q->next; \text{if}(p == q) p = h; free(q); $
  • 答案：D

解析：

  • 要删除非空单循环链表的第一个元素，需要先用临时指针q指向待删结点，然后将q从链表中断开，更新头指针的next指向第二个元素。若待删结点是链表的尾结点（即只有一个元素），则尾指针p需要指向头结点。因此，选项D正确考虑了这一特殊情况，并确保在删除结点后适当更新尾指针。

解答题

问题01：设计一个递归算法，删除不带头结点的单链表中所有值为x的结点。

解答

我们可以使用递归来遍历链表，并删除所有值为x的结点。算法的核心思路是：对于每个结点，检查它的值是否为x。如果是，则删除这个结点，并递归调用函数以处理剩余的链表；如果不是，则继续递归处理下一个结点。

递归模型

设 $ f(L, x) $ 的功能是删除以 $ L $ 为首结点的单链表中所有值等于x的结点。我们可以推导出以下递归模型：

  • 终止条件：如果链表为空（即 $ L == NULL $），则什么都不做，直接返回。
  • 递归主体：
    • 如果当前结点的值等于x，删除该结点，并递归调用 $ f(L->next, x) $ 处理剩余链表。
    • 如果当前结点的值不等于x，继续递归调用 $ f(L->next, x) $ 处理下一个结点。

代码实现

以下是递归删除单链表中所有值为x的结点的C++代码实现：

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
#include <iostream>
using namespace std;

struct LNode {
    int data;      // 数据域
    LNode *next;  // 指针域
};

// 删除单链表中所有值为x的结点
void DelX(LNode *&L, int x) {
    if (L == NULL) {
        return; // 递归出口：链表为空
    }
    // 如果当前结点的值等于x
    if (L->data == x) {
        LNode *p = L; // 指向待删除结点
        L = L->next;  // 更新头指针
        delete p;     // 释放内存
        DelX(L, x);   // 递归调用处理剩余链表
    } else {
        DelX(L->next, x); // 递归调用处理下一个结点
    }
}

// 辅助函数：创建链表并打印
void PrintList(LNode *L) {
    while (L != NULL) {
        cout << L->data << " ";
        L = L->next;
    }
    cout << endl;
}

// 主函数示例
int main() {
    // 创建一个示例链表
    LNode *head = new LNode{1, nullptr};
    head->next = new LNode{2, nullptr};
    head->next->next = new LNode{3, nullptr};
    head->next->next->next = new LNode{2, nullptr};
    head->next->next->next->next = new LNode{4, nullptr};

    cout << "原链表：";
    PrintList(head);

    int x = 2;
    DelX(head, x);

    cout << "删除值为 " << x << " 的结点后：";
    PrintList(head);

    // 释放剩余链表
    while (head != NULL) {
        LNode *temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}

答案和解释

  • 答案：代码正确实现了删除单链表中所有值为x的结点，算法的时间复杂度为 $ O(n) $，空间复杂度为 $ O(n) $（递归调用的深度）。
  • 解释：
    • 该算法使用了递归的方式处理链表，能够直接在原链表上进行操作，不会造成断链。
    • 递归出口确保当链表为空时结束递归。
    • 在删除结点时，通过更新当前结点的指针来维持链表的完整性，避免了内存泄漏。

问题02. 在带头结点的单链表中，删除所有值为x的结点，并释放其空间，假设值为x的结点不唯一，试编写算法以实现上述操作。

解答

有两种解法来实现此操作。

解法一：使用前驱指针

该方法使用指针 p 从头到尾扫描单链表，同时使用 pre 指向当前结点 p 的前驱。当 p 指向的结点值为 x 时，删除该结点并让 p 指向下一个结点；如果不是，则同时移动 pre 和 p 指针。

代码实现：

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
#include <iostream>
using namespace std;

struct LNode {
    int data;      // 数据域
    LNode *next;  // 指针域
};

void DelX1(LNode *L, int x) {
    // L 为带头结点的单链表，本算法删除链表中所有值为 x 的结点
    LNode *p = L->next; // p 指向第一个结点
    LNode *pre = L;     // pre 指向头结点
    LNode *q;           // q 用于存储待删除结点

    while (p != NULL) {
        if (p->data == x) {
            q = p;          // q 指向待删除结点
            p = p->next;   // p 移向下一个结点
            pre->next = p; // 前驱指针指向 p
            delete q;      // 释放待删除结点的空间
        } else {
            pre = p;       // 前驱指针和 p 指针同步后移
            p = p->next;
        }
    }
}

// 辅助函数：创建链表并打印
void PrintList(LNode *L) {
    while (L != NULL) {
        cout << L->data << " ";
        L = L->next;
    }
    cout << endl;
}

// 主函数示例
int main() {
    // 创建一个示例链表
    LNode *head = new LNode{0, nullptr}; // 头结点
    head->next = new LNode{1, nullptr};
    head->next->next = new LNode{2, nullptr};
    head->next->next->next = new LNode{3, nullptr};
    head->next->next->next->next = new LNode{2, nullptr};
    head->next->next->next->next->next = new LNode{4, nullptr};

    cout << "原链表：";
    PrintList(head->next);

    int x = 2;
    DelX1(head, x);

    cout << "删除值为 " << x << " 的结点后：";
    PrintList(head->next);

    // 释放剩余链表
    while (head != NULL) {
        LNode *temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}

解法二：使用尾插法重建链表

该方法使用指针 p 扫描链表，将所有值不为 x 的结点链接到一个新的链表中，并释放值为 x 的结点。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void DelX2(LNode *&L, int x) {
    // L 为带头结点的单链表，本算法删除链表中所有值为 x 的结点
    LNode *p = L->next; // p 指向第一个结点
    LNode *r = L;       // r 指向新的链表的尾部
    LNode *q;           // q 用于存储待删除结点

    while (p != NULL) {
        if (p->data != x) {
            r->next = p; // 连接不为 x 的结点
            r = p;       // 更新尾指针
            p = p->next; // 移动到下一个结点
        } else {
            q = p;       // q 指向待删除结点
            p = p->next; // 移动到下一个结点
            delete q;    // 释放空间
        }
    }
    r->next = NULL; // 最后将新的链表的尾部指向 NULL
}

// 示例代码同上，调用 DelX2() 函数来进行删除操作。

时间复杂度和空间复杂度

  • 时间复杂度：两种解法均为 $ O(n) $，其中 $ n $ 为链表中结点的数量，因为每个结点最多被访问一次。
  • 空间复杂度：两种解法均为 $ O(1) $，因为使用的额外空间是常量级别的，主要是指针变量。

问题03. 设工为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。

解答

有多种方法可以实现从尾到头反向输出单链表中的每个结点的值，以下是三种常见的解法：

  1. 链表逆置法：改变链表的方向，然后从头到尾输出。
  2. 使用栈：将每个结点的值压入栈中，最后从栈顶开始输出。
  3. 使用递归：通过递归调用实现从尾到头输出。

我们主要讨论最后两种方法，尤其是使用递归的实现方式。

方法 1：使用递归

该方法利用递归的特点，当访问到一个结点时，先递归输出后面的结点，然后再输出当前结点的值，从而实现反向输出。

代码实现：

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
#include <iostream>
using namespace std;

struct LNode {
    int data;      // 数据域
    LNode *next;  // 指针域
};

// 递归输出单链表中每个结点的值，从尾到头
void R_Print(LNode *L) {
    if (L != NULL) {               // 递归的基本条件
        R_Print(L->next);          // 先访问后面的结点
        if (L->next != NULL) {     // 避免输出头结点的值
            cout << L->data << " "; // 输出当前结点的值
        }
    }
}

// 辅助函数：创建链表并打印
void PrintList(LNode *L) {
    while (L != NULL) {
        cout << L->data << " ";
        L = L->next;
    }
    cout << endl;
}

// 主函数示例
int main() {
    // 创建一个示例链表
    LNode *head = new LNode{0, nullptr}; // 头结点
    head->next = new LNode{1, nullptr};
    head->next->next = new LNode{2, nullptr};
    head->next->next->next = new LNode{3, nullptr};
    head->next->next->next->next = new LNode{4, nullptr};

    cout << "原链表：";
    PrintList(head->next);

    cout << "反向输出链表的结点值：";
    R_Print(head->next); // 从头结点的下一个开始反向输出
    cout << endl;

    // 释放链表
    while (head != NULL) {
        LNode *temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}

方法 2：使用栈

该方法通过栈来存储链表中的每个结点的值。遍历完整个链表后，从栈顶开始输出结点的值。

代码实现：

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
#include <iostream>
#include <stack>
using namespace std;

struct LNode {
    int data;      // 数据域
    LNode *next;  // 指针域
};

// 使用栈从尾到头输出单链表中每个结点的值
void Stack_Print(LNode *L) {
    stack<int> s; // 创建栈
    LNode *p = L->next; // 从第一个结点开始遍历

    while (p != NULL) {
        s.push(p->data); // 将结点值压入栈
        p = p->next;     // 移动到下一个结点
    }

    // 从栈顶开始输出
    while (!s.empty()) {
        cout << s.top() << " "; // 输出栈顶元素
        s.pop();                // 弹出栈顶元素
    }
}

// 主函数示例
int main() {
    // 创建一个示例链表
    LNode *head = new LNode{0, nullptr}; // 头结点
    head->next = new LNode{1, nullptr};
    head->next->next = new LNode{2, nullptr};
    head->next->next->next = new LNode{3, nullptr};
    head->next->next->next->next = new LNode{4, nullptr};

    cout << "原链表：";
    PrintList(head->next);

    cout << "反向输出链表的结点值（使用栈）：";
    Stack_Print(head); // 从头结点的下一个开始反向输出
    cout << endl;

    // 释放链表
    while (head != NULL) {
        LNode *temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}

时间复杂度和空间复杂度

  • 时间复杂度：两种方法均为 $ O(n) $，其中 $ n $ 为链表中结点的数量，因为每个结点最多被访问一次。
  • 空间复杂度：
    • 递归方法：递归调用的深度最多为 $ O(n) $，因此空间复杂度为 $ O(n) $。
    • 栈方法：同样需要 $ O(n) $ 的空间来存储结点值。

问题04. 试编写在带头结点的单链表中删除一个最小值结点的高效算法（假设最小值结点是唯一的）。

解答

本算法的基本思想是使用两个指针：一个指针 p 用于遍历单链表，另一个指针 pre 指向 p 的前驱结点。同时，我们还需要两个指针 minp 和 minpre 来分别保存当前找到的最小值结点和它的前驱结点。算法步骤如下：

  1. 初始化 p 指向头结点的下一个结点，pre 指向头结点。
  2. 将 minp 和 minpre 初始化为 p 和 pre，以保存当前的最小值结点及其前驱。
  3. 遍历整个链表：
    • 如果当前结点的值小于 minp 的值，则更新 minp 和 minpre。
    • 否则，移动 pre 和 p 指针到下一个结点。
  4. 遍历结束后，minp 指向链表中唯一的最小值结点，minpre 指向它的前驱结点。
  5. 删除 minp 所指的结点，并释放其空间。

代码实现：

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
#include <iostream>
using namespace std;

struct LNode {
    int data;      // 数据域
    LNode *next;  // 指针域
};

typedef LNode* LinkList;

// 删除单链表中的最小值结点
LinkList DeleteMin(LinkList &L) {
    LNode *pre = L; // pre指向头结点
    LNode *p = pre->next; // p为工作指针
    LNode *minpre = pre; // minpre指向最小值结点的前驱
    LNode *minp = p; // minp指向当前最小值结点

    // 遍历链表，寻找最小值结点
    while (p != NULL) {
        if (p->data < minp->data) { // 如果当前结点值小于最小值
            minp = p; // 更新最小值结点
            minpre = pre; // 更新最小值结点的前驱
        }
        pre = p; // 移动前驱指针
        p = p->next; // 移动工作指针
    }

    // 删除最小值结点
    if (minp != NULL) {
        minpre->next = minp->next; // 让前驱结点的next指向最小值结点的下一个结点
        delete minp; // 释放最小值结点的空间
    }

    return L; // 返回链表头结点
}

// 辅助函数：创建链表并打印
void PrintList(LinkList L) {
    LNode *p = L->next; // 从第一个结点开始遍历
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 主函数示例
int main() {
    // 创建一个示例链表
    LinkList head = new LNode{0, nullptr}; // 头结点
    head->next = new LNode{3, nullptr};
    head->next->next = new LNode{1, nullptr};
    head->next->next->next = new LNode{4, nullptr};
    head->next->next->next->next = new LNode{2, nullptr};

    cout << "原链表：";
    PrintList(head);

    // 删除最小值结点
    DeleteMin(head);

    cout << "删除最小值结点后的链表：";
    PrintList(head);

    // 释放链表
    while (head != NULL) {
        LNode *temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}

时间复杂度和空间复杂度

  • 时间复杂度：该算法需要从头到尾遍历链表，因此时间复杂度为 $ O(n) $，其中 $ n $ 是链表中结点的数量。
  • 空间复杂度：由于只使用了有限的指针，空间复杂度为 $ O(1) $。

问题05. 试编写算法将带头结点的单链表就地逆置，所谓“就地”是指辅助空间复杂度为 $ O(1) $。

解答

要实现带头结点的单链表的就地逆置，可以采用两种方法：头插法和指针反转法。以下是对这两种方法的详细解释和实现代码。

解法一：头插法

通过将每个结点依次摘下，并插入到头结点之后，实现链表的逆置。具体步骤如下：

  1. 初始化指针 p 指向第一个结点，r 用于存储 p 的后继结点。
  2. 将头结点的 next 指针置为 NULL，表示链表暂时为空。
  3. 在遍历链表的过程中：
    • 将当前结点 p 的后继结点存储在 r 中。
    • 将 p 插入到头结点之后。
    • 更新 p 指针为 r，继续遍历。
  4. 重复上述步骤，直到遍历完整个链表。
代码实现：
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
#include <iostream>
using namespace std;

struct LNode {
    int data;      // 数据域
    LNode *next;  // 指针域
};

typedef LNode* LinkList;

// 使用头插法逆置单链表
LinkList Reverse1(LinkList &L) {
    LNode *p = L->next; // 工作指针，指向第一个结点
    L->next = NULL; // 初始化头结点的next为NULL

    while (p != NULL) {
        LNode *r = p->next; // 暂存后继结点
        p->next = L->next; // 将p插入到头结点之后
        L->next = p; // 更新头结点的next指针
        p = r; // 移动到下一个结点
    }

    return L; // 返回链表头结点
}

// 辅助函数：创建链表并打印
void PrintList(LinkList L) {
    LNode *p = L->next; // 从第一个结点开始遍历
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 主函数示例
int main() {
    // 创建一个示例链表
    LinkList head = new LNode{0, nullptr}; // 头结点
    head->next = new LNode{1, nullptr};
    head->next->next = new LNode{2, nullptr};
    head->next->next->next = new LNode{3, nullptr};
    head->next->next->next->next = new LNode{4, nullptr};

    cout << "原链表：";
    PrintList(head);

    // 逆置链表
    Reverse1(head);

    cout << "逆置后的链表：";
    PrintList(head);

    // 释放链表
    while (head != NULL) {
        LNode *temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}

解法二：指针反转法

该方法通过维护三个指针 pre、p 和 r，实现指针的反转。具体步骤如下：

  1. 初始化指针 p 指向第一个结点，r 指向 p 的下一个结点，pre 为 NULL。
  2. 将 p 的 next 指针置为 NULL，以便将它作为新的尾结点。
  3. 在遍历链表的过程中：
    • 将 r 设为 p 的下一个结点。
    • 将 p 的 next 指针指向 pre，实现指针反转。
    • 更新 pre 为当前的 p，将 p 更新为 r，继续遍历。
  4. 最后将头结点的 next 指针指向最后一个结点 p。
代码实现：
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
// 使用指针反转法逆置单链表
LinkList Reverse2(LinkList &L) {
    LNode *pre = NULL; // pre指针初始化为NULL
    LNode *p = L->next; // 工作指针，指向第一个结点
    LNode *r = p != NULL ? p->next : NULL; // 指向p的后继结点

    while (p != NULL) {
        p->next = pre; // 将当前结点的next指针指向前驱
        pre = p; // 更新前驱为当前结点
        p = r; // 移动到下一个结点
        r = (r != NULL) ? r->next : NULL; // 更新后继结点
    }

    L->next = pre; // 将头结点的next指针指向新的首结点
    return L; // 返回链表头结点
}

// 主函数示例
int main() {
    // 创建一个示例链表
    LinkList head = new LNode{0, nullptr}; // 头结点
    head->next = new LNode{1, nullptr};
    head->next->next = new LNode{2, nullptr};
    head->next->next->next = new LNode{3, nullptr};
    head->next->next->next->next = new LNode{4, nullptr};

    cout << "原链表：";
    PrintList(head);

    // 逆置链表
    Reverse2(head);

    cout << "逆置后的链表：";
    PrintList(head);

    // 释放链表
    while (head != NULL) {
        LNode *temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}

时间复杂度和空间复杂度

  • 时间复杂度：两个算法都需要遍历链表一次，因此时间复杂度为 $ O(n) $，其中 $ n $ 是链表中结点的数量。
  • 空间复杂度：这两个算法都只使用有限的指针，不需要额外的空间，因此空间复杂度为 $ O(1) $。

问题06. 有一个带头结点的单链表，设计一个算法使其元素递增有序。

解答

要将带头结点的单链表中的元素排序，可以采用直接插入排序的思想。算法的基本思路是：

  1. 构造初始有序链表：首先，创建一个只包含一个结点的有序链表（即链表的第一个实际元素）。
  2. 扫描剩余结点：然后依次扫描链表中剩下的结点 $ p $，并在已排序的链表中找到合适的位置（前驱结点 $ pre $），将当前结点 $ p $ 插入到 $ pre $ 之后。

代码实现

以下是实现上述思路的代码：

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
#include <iostream>
using namespace std;

struct LNode {
    int data;      // 数据域
    LNode *next;  // 指针域
};

typedef LNode* LinkList;

// 排序带头结点的单链表
void sort(LinkList &L) {
    LNode *p = L->next; // p指向第一个数据结点
    LNode *pre; // pre用来找到插入位置
    LNode *r = p->next; // r保持*p的后继结点指针

    // 将第一个结点的next指针置为NULL，构造只含一个数据结点的有序表
    p->next = NULL;

    while (p != NULL) {
        r = p->next; // 保存*p的后继结点指针
        pre = L; // 从头结点开始寻找插入位置

        // 查找插入位置，找到*p的前驱结点pre
        while (pre->next != NULL && pre->next->data < p->data) {
            pre = pre->next; // 移动pre
        }

        // 将*p插入到*pre之后
        p->next = pre->next;
        pre->next = p;

        // 更新p为下一个要处理的结点
        p = r;
    }
}

// 辅助函数：创建链表并打印
void PrintList(LinkList L) {
    LNode *p = L->next; // 从第一个结点开始遍历
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 主函数示例
int main() {
    // 创建一个示例链表
    LinkList head = new LNode{0, nullptr}; // 头结点
    head->next = new LNode{4, nullptr};
    head->next->next = new LNode{2, nullptr};
    head->next->next->next = new LNode{1, nullptr};
    head->next->next->next->next = new LNode{3, nullptr};

    cout << "原链表：";
    PrintList(head);

    // 排序链表
    sort(head);

    cout << "排序后的链表：";
    PrintList(head);

    // 释放链表
    while (head != NULL) {
        LNode *temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}

代码解释

  1. 初始化：

    • LNode *p = L->next;：指向链表中的第一个实际数据结点。
    • LNode *pre;：用于查找插入位置的前驱结点。
    • LNode *r = p->next;：保存当前结点的后继结点。

  2. 构建初始有序链表：

    • 将第一个结点的 next 指针置为 NULL，表示构造了一个只含有一个结点的有序链表。

  3. 主循环：

    • 遍历链表中的每个结点，直到处理完所有结点：
      • 使用 while 循环查找插入位置，找到 p 应该插入的位置的前驱结点 pre。
      • 将当前结点 p 插入到 pre 的后面。
      • 更新 p 为下一个结点 r。

时间复杂度和空间复杂度

  • 时间复杂度：该算法的时间复杂度为 $ O(n^2) $，因为在最坏情况下，每个结点都需要遍历已有的有序链表进行插入。
  • 空间复杂度：空间复杂度为 $ O(1) $，因为只使用了常数个指针。

改进方案

为了提高排序效率，可以考虑先将链表中的数据复制到数组中，使用更高效的排序算法（如归并排序、快速排序等）进行排序，然后再将排序后的元素依次插入到链表中。这样可以将时间复杂度降低到 $ O(n \log n) $，但空间复杂度会增加到 $ O(n) $，因为需要额外的数组来存储数据。

问题07. 设在一个带表头结点的单链表中所有元素结点的数据值无序，试编写一个函数，删除表中所有介于给定的两个值（作为函数参数给出）之间的元素（若存在）。

解答

由于链表是无序的，我们必须逐个遍历结点并检查每个结点的数据值。如果数据值介于给定的两个值之间，则需要删除该结点。下面是实现该功能的代码。

代码实现

以下是删除链表中介于给定两个值之间的元素的函数：

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
#include <iostream>
using namespace std;

struct LNode {
    int data;      // 数据域
    LNode *link;  // 指针域
};

typedef LNode* LinkList;

// 删除链表中介于min和max之间的元素
void RangeDelete(LinkList &L, int min, int max) {
    LNode *pr = L; // pr是前驱指针，初始化为头结点
    LNode *p = L->link; // p是当前结点指针，初始化为第一个数据结点

    while (p != NULL) {
        if (p->data > min && p->data < max) { // 如果数据值在范围内
            pr->link = p->link; // 删除结点
            delete p; // 释放内存
            p = pr->link; // 更新p为下一个结点
        } else {
            pr = p; // 更新前驱指针
            p = p->link; // 更新当前结点指针
        }
    }
}

// 辅助函数：创建链表并打印
void PrintList(LinkList L) {
    LNode *p = L->link; // 从第一个结点开始遍历
    while (p != NULL) {
        cout << p->data << " ";
        p = p->link;
    }
    cout << endl;
}

// 主函数示例
int main() {
    // 创建一个示例链表
    LinkList head = new LNode{0, nullptr}; // 头结点
    head->link = new LNode{5, nullptr};
    head->link->link = new LNode{3, nullptr};
    head->link->link->link = new LNode{8, nullptr};
    head->link->link->link->link = new LNode{2, nullptr};
    head->link->link->link->link->link = new LNode{6, nullptr};

    cout << "原链表：";
    PrintList(head);

    // 删除介于2和6之间的元素
    RangeDelete(head, 2, 6);

    cout << "删除后的链表：";
    PrintList(head);

    // 释放链表
    while (head != NULL) {
        LNode *temp = head;
        head = head->link;
        delete temp;
    }

    return 0;
}

代码解释

  1. 初始化：

    • LNode *pr = L;：前驱指针初始化为头结点。
    • LNode *p = L->link;：当前结点指针初始化为第一个数据结点。

  2. 主循环：

    • 使用 while (p != NULL) 遍历整个链表：
      • 如果当前结点的值在给定范围（min 和 max）之间，则执行删除操作。
        • pr->link = p->link;：将前驱结点的 link 指向当前结点的下一个结点，从而实现删除。
        • delete p;：释放当前结点的内存。
        • 更新 p 为下一个结点：p = pr->link;。
      • 如果当前结点的值不在范围内，则更新前驱指针和当前结点指针：
        • pr = p;
        • p = p->link;

时间复杂度和空间复杂度

  • 时间复杂度：该算法的时间复杂度为 $ O(n) $，因为我们需要遍历整个链表。
  • 空间复杂度：空间复杂度为 $ O(1) $，因为只使用了常数个指针。

示例输出

运行上述代码的结果将是：

1
2
原链表：5 3 8 2 6 
删除后的链表：5 8

这说明原链表中的值 3 和 2 被成功删除。

问题08. 给定两个单链表，编写算法找出两个链表的公共结点。

解答

两个单链表如果有公共结点，那么从某一结点开始，它们的 next 都指向同一个结点。为了找到这个公共结点，我们可以采用线性时间复杂度的算法。具体思路如下：

  1. 计算两个链表的长度，并确定哪个链表更长。
  2. 在较长的链表上先遍历长度差的结点，这样两个链表的指针在相同的位置开始同步遍历。
  3. 同时遍历两个链表，如果找到相同的结点，则返回该结点；如果遍历结束仍未找到，返回 NULL。

代码实现

以下是实现上述思路的代码：

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
#include <iostream>
using namespace std;

struct LNode {
    int data;      // 数据域
    LNode *next;  // 指针域
};

typedef LNode* LinkList;

// 计算链表长度
int Length(LinkList L) {
    int length = 0;
    LNode* p = L->next; // 从第一个数据结点开始
    while (p != NULL) {
        length++;
        p = p->next; // 遍历到下一个结点
    }
    return length;
}

// 找到两个链表的第一个公共结点
LinkList SearchFirstCommon(LinkList L1, LinkList L2) {
    int len1 = Length(L1); // 计算第一个链表的长度
    int len2 = Length(L2); // 计算第二个链表的长度

    LinkList longList, shortList; // 分别指向长链表和短链表
    int dist; // 表长之差

    // 确定长短链表
    if (len1 > len2) {
        longList = L1->next; // 长链表
        shortList = L2->next; // 短链表
        dist = len1 - len2; // 长短链表的长度差
    } else {
        longList = L2->next; // 长链表
        shortList = L1->next; // 短链表
        dist = len2 - len1; // 长短链表的长度差
    }

    // 在长链表上先遍历长度差个结点
    while (dist--) {
        longList = longList->next;
    }

    // 同步遍历两个链表，寻找第一个公共结点
    while (longList != NULL && shortList != NULL) {
        if (longList == shortList) { // 找到公共结点
            return longList; // 返回公共结点
        } else {
            longList = longList->next; // 向下一个结点移动
            shortList = shortList->next; // 向下一个结点移动
        }
    }

    return NULL; // 如果没有找到公共结点
}

// 辅助函数：创建链表并打印
void PrintList(LinkList L) {
    LNode *p = L->next; // 从第一个结点开始遍历
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 主函数示例
int main() {
    // 创建链表 L1
    LinkList L1 = new LNode{0, nullptr}; // 头结点
    L1->next = new LNode{1, nullptr};
    L1->next->next = new LNode{2, nullptr};
    
    // 创建链表 L2
    LinkList L2 = new LNode{0, nullptr}; // 头结点
    L2->next = new LNode{3, nullptr};
    L2->next->next = L1->next->next; // L2 和 L1 从结点 2 开始重合
    
    cout << "链表 L1: ";
    PrintList(L1);
    cout << "链表 L2: ";
    PrintList(L2);

    // 查找公共结点
    LinkList commonNode = SearchFirstCommon(L1, L2);
    
    if (commonNode) {
        cout << "第一个公共结点: " << commonNode->data << endl;
    } else {
        cout << "没有公共结点" << endl;
    }

    // 释放链表
    // 这里省略链表的内存释放以简化示例

    return 0;
}

代码解释

  1. 长度计算：

    • Length(LinkList L)：计算链表的长度。

  2. 寻找公共结点：

    • 使用 SearchFirstCommon(LinkList L1, LinkList L2) 函数找到两个链表的第一个公共结点。
    • 首先计算两个链表的长度，并确定哪个更长。
    • 在长链表上先移动长度差的结点，使得两个链表在同一位置开始遍历。
    • 然后同时遍历两个链表，若找到相同的结点，则返回该结点；若遍历结束仍未找到，则返回 NULL。

时间复杂度和空间复杂度

  • 时间复杂度：该算法的时间复杂度为 $ O(len1 + len2) $，因为需要遍历两个链表。
  • 空间复杂度：空间复杂度为 $ O(1) $，只使用了常数个指针。

示例输出

运行上述代码的结果将是：

1
2
3
链表 L1: 1 2 
链表 L2: 3 2 
第一个公共结点: 2

这说明链表 L1 和 L2 的第一个公共结点的值为 2。

问题09. 给定一个带表头结点的单链表，设 head 为头指针，结点结构为 (data, next)，data 为整型元素，next 为指针。试写出算法: 按递增次序输出单链表中各结点的数据元素并释放结点所占的存储空间 (要求: 不允许使用数组作为辅助空间)。

解答

算法思想：
通过遍历链表，逐步找出链表中的最小值，输出该值并释放其占用的存储空间。重复这个过程，直到链表为空。最后释放头结点所占的空间。

时间复杂度：该算法的时间复杂度为 $O(n^2)$，其中 $n$ 是链表的结点数。这是因为每次查找最小值都需要遍历剩余的结点。

代码实现

以下是实现上述思路的代码：

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
#include <iostream>
using namespace std;

struct LNode {
    int data;      // 数据域
    LNode *next;  // 指针域
};

typedef LNode* LinkList;

// 按递增顺序输出单链表中的数据元素并释放结点空间
void MinDelete(LinkList &head) {
    while (head->next != NULL) { // 循环到仅剩头结点
        LNode *pre = head; // pre为当前最小值结点的前驱结点
        LNode *p = pre->next; // p 为工作指针

        // 查找当前链表的最小值
        while (p != NULL) {
            if (p->data < pre->next->data) {
                pre = p; // 记住当前最小值结点的前驱
            }
            p = p->next; // 移动到下一个结点
        }

        // 输出当前最小值结点的数据
        cout << pre->next->data << " ";

        // 删除当前最小值结点，释放结点空间
        LNode *u = pre->next;
        pre->next = u->next; // 修改前驱结点的指针
        free(u); // 释放结点空间
    }

    free(head); // 释放头结点
}

// 辅助函数：创建链表并打印
LinkList CreateList(int arr[], int n) {
    LinkList head = new LNode{0, nullptr}; // 头结点
    LNode *tail = head; // 尾指针
    for (int i = 0; i < n; ++i) {
        LNode *newNode = new LNode{arr[i], nullptr};
        tail->next = newNode;
        tail = newNode; // 移动到新添加的结点
    }
    return head;
}

// 主函数示例
int main() {
    int arr[] = {3, 1, 4, 2}; // 示例数据
    LinkList head = CreateList(arr, 4); // 创建链表

    cout << "链表中的元素按递增顺序输出: ";
    MinDelete(head); // 按递增顺序输出并释放结点空间
    cout << endl;

    return 0;
}

代码解释

  1. 结点结构：

    • struct LNode 定义了链表结点的数据结构。

  2. MinDelete 函数：

    • MinDelete(LinkList &head)：该函数通过循环查找链表中的最小值，输出并释放该结点的存储空间。
    • 在外层 while 循环中，继续遍历链表，直到只剩下头结点。
    • 在内层 while 循环中，查找当前链表中的最小值，并更新 pre 指针指向该最小值的前驱结点。
    • 找到最小值后，输出该值，调整指针，释放结点空间。

  3. 辅助函数：

    • CreateList(int arr[], int n)：该函数用于根据数组创建链表。

  4. 主函数：

    • main() 中创建了一个示例链表，并调用 MinDelete 函数输出链表中的元素。

示例输出

运行上述代码的结果将是：

1
链表中的元素按递增顺序输出: 1 2 3 4

这说明链表中的元素按递增顺序成功输出，并释放了所有结点的存储空间。

问题10. 将一个带头结点的单链表 $A$ 分解为两个带头结点的单链表 $A’$ 和 $B$，使得 $A’$ 表中含有原表中序号为奇数的元素，而 $B$ 表中含有原表中序号为偶数的元素，且保持其相对顺序不变。

解答

算法思想：
使用一个访问序号变量（初始值为0），在遍历链表的每个结点时，序号自动加1。根据序号的奇偶性将结点插入到 $A’$ 表或 $B$ 表中。重复此操作直到遍历完链表。

时间复杂度：该算法的时间复杂度为 $O(n)$，其中 $n$ 是链表的结点数。

代码实现

以下是实现上述思路的代码：

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
#include <iostream>
using namespace std;

struct LNode {
    int data;      // 数据域
    LNode *next;  // 指针域
};

typedef LNode* LinkList;

// 将链表 A 分解为两个链表 A' 和 B
void DisCreate(LinkList &A, LinkList &B) {
    int i = 0; // 记录结点序号
    B = new LNode{0, nullptr}; // 创建 B 表的头结点
    LNode *ra = A; // ra 指向新的 A' 表的尾结点
    LNode *rb = B; // rb 指向新的 B 表的尾结点
    LNode *p = A->next; // p 为链表工作指针，指向待分解的结点

    // 遍历链表 A
    while (p != nullptr) {
        i++; // 序号加1

        if (i % 2 == 1) { // 奇数序号
            ra->next = p; // 将结点插入 A' 表
            ra = p; // 更新 ra 指针
        } else { // 偶数序号
            rb->next = p; // 将结点插入 B 表
            rb = p; // 更新 rb 指针
        }

        p = p->next; // 移动到下一个结点
    }

    // 结束 A' 表和 B 表
    ra->next = nullptr; // 终止 A' 表
    rb->next = nullptr; // 终止 B 表
}

// 辅助函数：创建链表并打印
LinkList CreateList(int arr[], int n) {
    LinkList head = new LNode{0, nullptr}; // 头结点
    LNode *tail = head; // 尾指针
    for (int i = 0; i < n; ++i) {
        LNode *newNode = new LNode{arr[i], nullptr};
        tail->next = newNode;
        tail = newNode; // 移动到新添加的结点
    }
    return head;
}

// 辅助函数：打印链表
void PrintList(LinkList head) {
    LNode *p = head->next; // 跳过头结点
    while (p != nullptr) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 主函数示例
int main() {
    int arr[] = {1, 2, 3, 4, 5}; // 示例数据
    LinkList A = CreateList(arr, 5); // 创建链表 A
    LinkList B; // 声明链表 B

    DisCreate(A, B); // 将链表 A 分解为链表 A' 和 B

    cout << "链表 A' 中的元素: ";
    PrintList(A); // 打印链表 A'

    cout << "链表 B 中的元素: ";
    PrintList(B); // 打印链表 B

    // 释放链表内存
    delete A; // 释放 A 的头结点
    delete B; // 释放 B 的头结点

    return 0;
}

代码解释

  1. 结点结构：

    • struct LNode 定义了链表结点的数据结构。

  2. DisCreate 函数：

    • DisCreate(LinkList &A, LinkList &B)：该函数根据奇偶性将链表 $A$ 分解为链表 $A’$ 和 $B$。
    • 使用 i 记录当前结点的序号。每访问一个结点，序号加1。
    • 根据序号的奇偶性，将结点插入到相应的链表 $A’$ 或 $B$ 中。
    • 最后，分别将 $A’$ 和 $B$ 的尾结点的 next 指针设为 nullptr。

  3. 辅助函数：

    • CreateList(int arr[], int n)：该函数用于根据数组创建链表。
    • PrintList(LinkList head)：该函数用于打印链表的元素。

  4. 主函数：

    • main() 中创建了一个示例链表 $A$，调用 DisCreate 函数将其分解为链表 $A’$ 和 $B$，然后打印两个链表的内容。

示例输出

运行上述代码的结果将是：

1
2
链表 A' 中的元素: 1 3 5 
链表 B 中的元素: 2 4

这表明链表 $A$ 成功分解为两个链表，$A’$ 中包含原链表中序号为奇数的元素，$B$ 中包含序号为偶数的元素，并保持了相对顺序不变。

问题11. 设 $ C=\{a_1, b_1, a_2, b_2, \ldots, a_n, b_n\} $ 为线性表，采用带头结点的单链表存放，设计一个就地算法，将其拆分为两个线性表，使得 $ A=\{a_1, a_2, \ldots, a_n\} $，$ B=\{b_1, b_2, \ldots, b_n\} $。

解答

算法思想：
本算法采用与前一题相似的思路，不设序号变量。由于 $ B $ 表的建立采用头插法，因此每次将新结点插入到 $ B $ 的表头。这种方法可以在遍历时直接修改原链表的结构，同时保持 $ A $ 和 $ B $ 的顺序。

时间复杂度：该算法的时间复杂度为 $ O(n) $，其中 $ n $ 是链表的结点数。

代码实现

以下是实现上述思路的代码：

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
#include <iostream>
using namespace std;

struct LNode {
    char data;      // 数据域
    LNode *next;   // 指针域
};

typedef LNode* LinkList;

// 将线性表 C 拆分为 A 和 B
LinkList DisCreate2(LinkList &C) {
    LinkList B = new LNode{0, nullptr}; // 创建 B 表的头结点
    LNode *ra = C; // ra 指向 A 表的尾结点
    LNode *p = C->next; // p 为链表工作指针

    while (p != nullptr) {
        ra->next = p; // 将 *p 链接到 A 的表尾
        ra = p; // 更新 A 表的尾结点
        p = p->next; // 移动到下一个待处理的结点

        // 处理 B 表
        if (p != nullptr) {
            LNode *q = p->next; // 记住 p 的后继
            p->next = B->next; // 将 *p 插入到 B 的前端
            B->next = p; // 更新 B 的表头
            p = q; // 更新 p 为下一个待处理结点
        }
    }

    ra->next = nullptr; // 终止 A 表
    return B; // 返回 B 表
}

// 辅助函数：创建链表并打印
LinkList CreateList(char arr[], int n) {
    LinkList head = new LNode{0, nullptr}; // 头结点
    LNode *tail = head; // 尾指针
    for (int i = 0; i < n; ++i) {
        LNode *newNode = new LNode{arr[i], nullptr};
        tail->next = newNode;
        tail = newNode; // 移动到新添加的结点
    }
    return head;
}

// 辅助函数：打印链表
void PrintList(LinkList head) {
    LNode *p = head->next; // 跳过头结点
    while (p != nullptr) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 主函数示例
int main() {
    char arr[] = {'a', 'b', 'c', 'd', 'e', 'f'}; // 示例数据
    LinkList C = CreateList(arr, 6); // 创建链表 C
    LinkList B; // 声明链表 B

    B = DisCreate2(C); // 拆分链表 C 为 A 和 B

    cout << "链表 A 中的元素: ";
    PrintList(C); // 打印链表 A

    cout << "链表 B 中的元素: ";
    PrintList(B); // 打印链表 B

    // 释放链表内存
    delete C; // 释放 C 的头结点
    delete B; // 释放 B 的头结点

    return 0;
}

代码解释

  1. 结点结构：

    • struct LNode 定义了链表结点的数据结构，包含数据域和指针域。

  2. DisCreate2 函数：

    • DisCreate2(LinkList &C)：该函数根据链表 $C$ 拆分出链表 $A$ 和链表 $B$。
    • LinkList B = new LNode{0, nullptr};：创建链表 $B$ 的头结点。
    • LNode *ra = C;：ra 指向 $A$ 的尾结点。
    • LNode *p = C->next;：p 为工作指针，指向待处理的结点。
    • 在 while 循环中：
      • 将当前结点链接到 $A$ 的尾部，并更新尾指针 ra。
      • 如果 p 的下一个结点存在，则将当前结点链接到 $B$ 的头部。
      • 使用 q 保存下一个待处理的结点，以避免链表断链。
    • 最后，终止 $A$ 的链表并返回 $B$ 的头结点。

  3. 辅助函数：

    • CreateList(char arr[], int n)：根据字符数组创建链表。
    • PrintList(LinkList head)：打印链表的元素。

  4. 主函数：

    • main() 中创建了一个示例链表 $C$，调用 DisCreate2 拆分为链表 $A$ 和 $B$，然后打印两个链表的内容。

示例输出

运行上述代码的结果将是：

1
2
链表 A 中的元素: a c e 
链表 B 中的元素: f d b

这表明链表 $C$ 成功拆分为两个链表，$A$ 中包含原链表中 $a$ 的元素，$B$ 中包含 $b$ 的元素，且保持了相对顺序不变。

问题12:在一个递增有序的线性表中，存在数值相同的元素。若存储方式为单链表，设计一个算法去掉数值相同的元素，使表中不再有重复的元素。例如，输入为 (7, 10, 10, 21, 30, 42, 42, 42, 51, 70)，将变为 (7, 10, 21, 30, 42, 51, 70)。

解答

算法思想

由于链表是递增有序的，因此所有相同值域的结点都是相邻的。我们可以使用一个指针 $p$ 来扫描链表，如果当前结点的值与后继结点的值相同，则删除后继结点，否则移动指针 $p$ 到下一个结点。

代码实现

以下是 C++ 代码示例，用于实现上述算法：

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
#include <iostream>
using namespace std;

struct LNode {
    int data;         // 数据域
    LNode *next;     // 指针域
};

typedef LNode* LinkList;

// 删除单链表中重复的元素
void DelSame(LinkList &l) {
    LNode *p = l->next; // 工作指针，跳过头结点
    LNode *q;           // 用于指向后继结点

    while (p != nullptr && p->next != nullptr) {
        q = p->next; // q 指向 p 的后继结点
        if (p->data == q->data) { // 找到重复值的结点
            p->next = q->next;    // 删除 q 结点
            delete q;             // 释放内存
        } else {
            p = p->next;          // 移动 p 到下一个结点
        }
    }
}

// 辅助函数：创建链表并打印
LinkList CreateList(int arr[], int n) {
    LinkList head = new LNode{0, nullptr}; // 创建头结点
    LNode *tail = head; // 尾指针
    for (int i = 0; i < n; ++i) {
        LNode *newNode = new LNode{arr[i], nullptr};
        tail->next = newNode; // 在链表尾部插入新结点
        tail = newNode;       // 更新尾指针
    }
    return head;
}

// 辅助函数：打印链表
void PrintList(LinkList head) {
    LNode *p = head->next; // 跳过头结点
    while (p != nullptr) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 主函数示例
int main() {
    int arr[] = {7, 10, 10, 21, 30, 42, 42, 42, 51, 70}; // 示例数据
    LinkList l = CreateList(arr, 10); // 创建链表

    cout << "原始链表: ";
    PrintList(l); // 打印原始链表

    DelSame(l); // 删除重复元素

    cout << "去重后的链表: ";
    PrintList(l); // 打印去重后的链表

    // 释放链表内存
    LNode *p = l;
    while (p != nullptr) {
        LNode *temp = p;
        p = p->next;
        delete temp; // 逐个释放结点
    }

    return 0;
}

代码说明

  • DelSame 函数：通过遍历链表，检查当前结点与下一个结点的值是否相等。如果相等，删除下一个结点；否则，继续移动指针到下一个结点。这样可以在单链表中去除所有重复的元素。

  • 辅助函数：CreateList 用于创建链表，PrintList 用于打印链表的元素。

时间与空间复杂度

  • 时间复杂度：$O(n)$，因为每个结点仅被访问一次。
  • 空间复杂度：$O(1)$，不使用额外的存储空间。

示例输出

运行该代码，输出将为：

1
2
原始链表: 7 10 10 21 30 42 42 42 51 70 
去重后的链表: 7 10 21 30 42 51 70

问题13:假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

解答

算法思想

由于两个链表已经按元素值递增排序，我们可以同时从两个链表的头结点开始进行比较。每次将较小的结点插入到新链表的头部，以达到按元素值递减的顺序。比较结束后，可能会有一个链表非空，此时将剩下的结点依次插入新链表中。归并后的链表采用头插法实现。

代码实现

以下是 C++ 代码示例，用于实现上述算法：

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
#include <iostream>
using namespace std;

struct LNode {
    int data;         // 数据域
    LNode *next;     // 指针域
};

typedef LNode* LinkList;

// 合并两个递增有序链表，生成按元素值递减排序的链表
void MergeList(LinkList &La, LinkList &Lb) {
    LNode *r, *pa = La->next, *pb = Lb->next;

    La->next = nullptr; // 初始化结果链表为空

    // 当两个链表均不为空时，循环
    while (pa && pb) {
        if (pa->data <= pb->data) {
            r = pa->next; // 暂存 pa 的后继结点指针
            pa->next = La->next; // 将 pa 结点链入结果表中
            La->next = pa; // 头插法
            pa = r; // 恢复 pa 为当前待比较结点
        } else {
            r = pb->next; // 暂存 pb 的后继结点指针
            pb->next = La->next; // 将 pb 结点链入结果表中
            La->next = pb; // 头插法
            pb = r; // 恢复 pb 为当前待比较结点
        }
    }

    // 处理剩下的一个非空链表
    while (pa) {
        r = pa->next; // 暂存 pa 的后继结点
        pa->next = La->next; // 将 pa 结点链入结果表中
        La->next = pa; // 头插法
        pa = r; // 恢复 pa 为当前待比较结点
    }

    while (pb) {
        r = pb->next; // 暂存 pb 的后继结点
        pb->next = La->next; // 将 pb 结点链入结果表中
        La->next = pb; // 头插法
        pb = r; // 恢复 pb 为当前待比较结点
    }

    // 释放 Lb 链表的头结点
    delete Lb; 
    Lb = nullptr; // 防止悬空指针
}

// 辅助函数：创建链表并打印
LinkList CreateList(int arr[], int n) {
    LinkList head = new LNode{0, nullptr}; // 创建头结点
    LNode *tail = head; // 尾指针
    for (int i = 0; i < n; ++i) {
        LNode *newNode = new LNode{arr[i], nullptr};
        tail->next = newNode; // 在链表尾部插入新结点
        tail = newNode;       // 更新尾指针
    }
    return head;
}

// 辅助函数：打印链表
void PrintList(LinkList head) {
    LNode *p = head->next; // 跳过头结点
    while (p != nullptr) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 主函数示例
int main() {
    int arr1[] = {1, 3, 5, 7}; // 第一个递增链表
    int arr2[] = {2, 4, 6, 8}; // 第二个递增链表

    LinkList La = CreateList(arr1, 4); // 创建第一个链表
    LinkList Lb = CreateList(arr2, 4); // 创建第二个链表

    cout << "第一个链表: ";
    PrintList(La); // 打印第一个链表

    cout << "第二个链表: ";
    PrintList(Lb); // 打印第二个链表

    MergeList(La, Lb); // 合并两个链表

    cout << "合并后的链表: ";
    PrintList(La); // 打印合并后的链表

    // 释放链表内存
    LNode *p = La;
    while (p != nullptr) {
        LNode *temp = p;
        p = p->next;
        delete temp; // 逐个释放结点
    }

    return 0;
}

代码说明

  • MergeList 函数：通过遍历两个链表，依次将较小的结点插入到结果链表的头部，以实现按元素值递减的顺序。最后处理剩下的结点，并释放第二个链表的头结点。

  • 辅助函数：CreateList 用于创建链表，PrintList 用于打印链表的元素。

时间与空间复杂度

  • 时间复杂度：$O(m+n)$，其中 $m$ 和 $n$ 分别为两个链表的结点数。
  • 空间复杂度：$O(1)$，只使用了常量级的额外空间。

示例输出

运行该代码，输出将为：

1
2
3
第一个链表: 1 3 5 7 
第二个链表: 2 4 6 8 
合并后的链表: 8 7 6 5 4 3 2 1

问题14:设 A 和 B 是两个单链表（带头结点），其中元素递增有序。设计一个算法从 A 和 B 中的公共元素产生单链表 C，要求不破坏 A 和 B 的结点。

解答

算法思想

由于链表 A 和 B 都是有序的，我们可以使用两个指针分别遍历这两个链表，依次比较它们的元素值。如果元素值相等，就创建一个新结点并将其插入到链表 C 中。如果元素值不相等，则将指向较小元素的指针后移，继续比较。该过程持续进行，直到遍历到其中一个链表的尾部。

代码实现

以下是 C++ 代码示例，用于实现上述算法：

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
#include <iostream>
using namespace std;

struct LNode {
    int data;         // 数据域
    LNode *next;     // 指针域
};

typedef LNode* LinkList;

// 从链表 A 和 B 中产生公共元素的链表 C
void GetCommon(LinkList A, LinkList B, LinkList &C) {
    LNode *p = A->next; // A 的工作指针
    LNode *q = B->next; // B 的工作指针
    LNode *r = C;       // C 的尾指针

    // 循环条件：同时遍历 A 和 B
    while (p != nullptr && q != nullptr) {
        if (p->data < q->data) {
            p = p->next; // A 当前元素较小，后移指针
        } else if (p->data > q->data) {
            q = q->next; // B 当前元素较小，后移指针
        } else {
            // 找到公共元素
            LNode *s = new LNode; // 创建新结点
            s->data = p->data;    // 复制公共元素值
            r->next = s;          // 将新结点链接到 C 上
            r = s;                // 更新尾指针
            p = p->next;         // 继续遍历
            q = q->next;         // 继续遍历
        }
    }
    r->next = nullptr; // 结束链表 C
}

// 辅助函数：创建链表并打印
LinkList CreateList(int arr[], int n) {
    LinkList head = new LNode{0, nullptr}; // 创建头结点
    LNode *tail = head; // 尾指针
    for (int i = 0; i < n; ++i) {
        LNode *newNode = new LNode{arr[i], nullptr};
        tail->next = newNode; // 在链表尾部插入新结点
        tail = newNode;       // 更新尾指针
    }
    return head;
}

// 辅助函数：打印链表
void PrintList(LinkList head) {
    LNode *p = head->next; // 跳过头结点
    while (p != nullptr) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 主函数示例
int main() {
    int arrA[] = {1, 2, 3, 4, 5}; // 第一个递增链表
    int arrB[] = {3, 4, 5, 6, 7}; // 第二个递增链表

    LinkList A = CreateList(arrA, 5); // 创建第一个链表
    LinkList B = CreateList(arrB, 5); // 创建第二个链表
    LinkList C = new LNode{0, nullptr}; // 创建结果链表头结点

    cout << "链表 A: ";
    PrintList(A); // 打印链表 A

    cout << "链表 B: ";
    PrintList(B); // 打印链表 B

    GetCommon(A, B, C); // 获取公共元素的链表 C

    cout << "公共元素链表 C: ";
    PrintList(C); // 打印链表 C

    // 释放链表内存
    LNode *p = A;
    while (p != nullptr) {
        LNode *temp = p;
        p = p->next;
        delete temp; // 逐个释放链表 A 的结点
    }

    p = B;
    while (p != nullptr) {
        LNode *temp = p;
        p = p->next;
        delete temp; // 逐个释放链表 B 的结点
    }

    p = C;
    while (p != nullptr) {
        LNode *temp = p;
        p = p->next;
        delete temp; // 逐个释放链表 C 的结点
    }

    return 0;
}

代码说明

  • GetCommon 函数：通过遍历链表 A 和 B，查找公共元素，并使用尾插法将公共元素插入到链表 C 中。

  • 辅助函数：CreateList 用于创建链表，PrintList 用于打印链表的元素。

时间与空间复杂度

  • 时间复杂度：$O(m+n)$，其中 $m$ 和 $n$ 分别为两个链表的结点数。
  • 空间复杂度：$O(1)$，只使用了常量级的额外空间，除了新创建的公共元素结点外。

示例输出

运行该代码，输出将为：

1
2
3
链表 A: 1 2 3 4 5 
链表 B: 3 4 5 6 7 
公共元素链表 C: 3 4 5

问题15:已知两个链表 $ A $ 和 $ B $ 分别表示两个集合，其元素递增排列。编制函数，求 $ A $ 与 $ B $ 的交集，并存放于 $ A $ 链表中。

解答

算法思想

采用归并的思想，设置两个工作指针 $ pa $ 和 $ pb $，对两个链表进行归并扫描。只有同时出现在两个集合中的元素才链接到结果表中且仅保留一个，其他的结点全部释放。当一个链表遍历完毕后，释放另一个表中剩下的全部结点。

代码实现

以下是 C++ 代码示例，用于实现上述算法：

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
#include <iostream>
using namespace std;

struct LNode {
    int data;         // 数据域
    LNode *next;     // 指针域
};

typedef LNode* LinkList;

// 求链表 A 和 B 的交集，并存放于 A 中
LinkList Union(LinkList &A, LinkList &B) {
    LNode *pa = A->next; // A 的工作指针
    LNode *pb = B->next; // B 的工作指针
    LNode *pc = A;       // 结果表中当前合并结点的前驱指针

    while (pa && pb) {
        if (pa->data == pb->data) {
            // A 中结点链接到结果表
            pc->next = pa;
            pc = pa;            // 更新结果链表的尾指针
            pa = pa->next;     // 移动 A 的指针
            LNode *u = pb;     // 释放 B 中当前结点
            pb = pb->next;
            delete u;         // 释放当前 B 中结点
        } else if (pa->data < pb->data) {
            // A 中当前结点值小于 B 中当前结点值
            LNode *u = pa;     // 释放 A 中当前结点
            pa = pa->next;
            delete u;         // 释放当前 A 中结点
        } else {
            // B 中当前结点值小于 A 中当前结点值
            LNode *u = pb;     // 释放 B 中当前结点
            pb = pb->next;
            delete u;         // 释放当前 B 中结点
        }
    }

    // 释放剩余结点
    while (pa) {
        LNode *u = pa;  // 释放 A 中剩余结点
        pa = pa->next;
        delete u;       // 释放当前 A 中结点
    }

    while (pb) {
        LNode *u = pb;  // 释放 B 中剩余结点
        pb = pb->next;
        delete u;       // 释放当前 B 中结点
    }

    pc->next = nullptr; // 结果链表尾指针指向 NULL
    delete B;           // 释放 B 的头结点

    return A; // 返回链表 A
}

// 辅助函数：创建链表并打印
LinkList CreateList(int arr[], int n) {
    LinkList head = new LNode{0, nullptr}; // 创建头结点
    LNode *tail = head; // 尾指针
    for (int i = 0; i < n; ++i) {
        LNode *newNode = new LNode{arr[i], nullptr};
        tail->next = newNode; // 在链表尾部插入新结点
        tail = newNode;       // 更新尾指针
    }
    return head;
}

// 辅助函数：打印链表
void PrintList(LinkList head) {
    LNode *p = head->next; // 跳过头结点
    while (p != nullptr) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 主函数示例
int main() {
    int arrA[] = {1, 2, 3, 4, 5}; // 第一个递增链表
    int arrB[] = {3, 4, 5, 6, 7}; // 第二个递增链表

    LinkList A = CreateList(arrA, 5); // 创建第一个链表
    LinkList B = CreateList(arrB, 5); // 创建第二个链表

    cout << "链表 A: ";
    PrintList(A); // 打印链表 A

    cout << "链表 B: ";
    PrintList(B); // 打印链表 B

    Union(A, B); // 求 A 和 B 的交集并存放在 A 中

    cout << "交集链表 A: ";
    PrintList(A); // 打印交集链表 A

    // 释放链表内存
    LNode *p = A;
    while (p != nullptr) {
        LNode *temp = p;
        p = p->next;
        delete temp; // 逐个释放链表 A 的结点
    }

    return 0;
}

代码说明

  • Union 函数：通过遍历链表 $ A $ 和 $ B $，查找公共元素，并将公共元素插入到链表 $ A $ 中。非公共元素会被释放。

  • 辅助函数：CreateList 用于创建链表，PrintList 用于打印链表的元素。

时间与空间复杂度

  • 时间复杂度：$ O(lenA + lenB) $，其中 $ lenA $ 和 $ lenB $ 分别为两个链表的结点数。
  • 空间复杂度：$ O(1) $，只使用了常量级的额外空间，除了新创建的公共元素结点外。

示例输出

运行该代码，输出将为：

1
2
3
链表 A: 1 2 3 4 5 
链表 B: 3 4 5 6 7 
交集链表 A: 3 4 5

问题16:已知两个整数序列 $ A = a_1, a_2, a_3, \ldots, a_m $ 和 $ B = b_1, b_2, b_3, \ldots, b_n $，已经存入两个单链表中。设计一个算法，判断序列 $ B $ 是否是序列 $ A $ 的连续子序列。

解答

算法思想

从两个链表的第一个结点开始进行比较。若对应的数据相等，则后移指针；若不等，则链表 $ A $ 的指针从上次比较结点的后继开始，链表 $ B $ 的指针仍从第一个结点开始比较。若链表 $ B $ 到达尾部而 $ A $ 还未到尾，则表示匹配成功；否则，若 $ A $ 到达尾部而 $ B $ 未到尾，则表示匹配失败。

代码实现

以下是 C++ 代码示例，用于实现上述算法：

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
#include <iostream>
using namespace std;

struct LNode {
    int data;         // 数据域
    LNode *next;     // 指针域
};

typedef LNode* LinkList;

// 判断 B 是否是 A 的连续子序列
int Pattern(LinkList A, LinkList B) {
    LNode *p = A; // A 的工作指针
    LNode *q = B; // B 的工作指针

    // 遍历 A 和 B
    while (p) {
        LNode *pre = p; // 记住 A 的当前开始结点
        q = B;          // B 始终从头开始

        // 比较 A 的当前结点与 B 的所有结点
        while (p && q && p->data == q->data) {
            p = p->next; // 如果相等，移动 A 的指针
            q = q->next; // 移动 B 的指针
        }

        // 如果 B 已经比较结束，说明 B 是 A 的子序列
        if (q == nullptr) {
            return 1; // 匹配成功
        }

        // 否则，继续从 A 的下一个结点开始比较
        p = pre->next;
    }

    return 0; // 匹配失败
}

// 辅助函数：创建链表并打印
LinkList CreateList(int arr[], int n) {
    LinkList head = new LNode{0, nullptr}; // 创建头结点
    LNode *tail = head; // 尾指针
    for (int i = 0; i < n; ++i) {
        LNode *newNode = new LNode{arr[i], nullptr};
        tail->next = newNode; // 在链表尾部插入新结点
        tail = newNode;       // 更新尾指针
    }
    return head;
}

// 辅助函数：打印链表
void PrintList(LinkList head) {
    LNode *p = head->next; // 跳过头结点
    while (p != nullptr) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 主函数示例
int main() {
    int arrA[] = {1, 2, 3, 4, 5}; // 链表 A
    int arrB[] = {3, 4};          // 链表 B

    LinkList A = CreateList(arrA, 5); // 创建链表 A
    LinkList B = CreateList(arrB, 2); // 创建链表 B

    cout << "链表 A: ";
    PrintList(A); // 打印链表 A

    cout << "链表 B: ";
    PrintList(B); // 打印链表 B

    if (Pattern(A, B)) {
        cout << "B 是 A 的连续子序列" << endl;
    } else {
        cout << "B 不是 A 的连续子序列" << endl;
    }

    // 释放链表内存
    LNode *p = A;
    while (p != nullptr) {
        LNode *temp = p;
        p = p->next;
        delete temp; // 逐个释放链表 A 的结点
    }

    p = B;
    while (p != nullptr) {
        LNode *temp = p;
        p = p->next;
        delete temp; // 逐个释放链表 B 的结点
    }

    return 0;
}

代码说明

  • Pattern 函数：通过遍历链表 $ A $ 和 $ B $，判断 $ B $ 是否是 $ A $ 的连续子序列。若找到连续匹配，则返回 1，表示成功；否则，继续比较。

  • 辅助函数：CreateList 用于创建链表，PrintList 用于打印链表的元素。

时间与空间复杂度

  • 时间复杂度：在最坏情况下，时间复杂度为 $ O(m \times n) $，其中 $ m $ 是链表 $ A $ 的长度，$ n $ 是链表 $ B $ 的长度。

  • 空间复杂度：$ O(1) $，只使用了常量级的额外空间。

示例输出

运行该代码，输出将为：

1
2
3
链表 A: 1 2 3 4 5 
链表 B: 3 4 
B 是 A 的连续子序列

问题17:有两个循环单链表，链表头指针分别为 $ h_1 $ 和 $ h_2 $。编写一个函数将链表 $ h_2 $ 链接到链表 $ h_1 $ 之后，要求链接后的链表仍保持循环链表的形式。

解答

算法思想

  1. 首先，找到链表 $ h_1 $ 的尾结点和链表 $ h_2 $ 的尾结点。
  2. 将链表 $ h_1 $ 的尾结点的 next 指针指向链表 $ h_2 $ 的头结点。
  3. 然后，将链表 $ h_2 $ 的尾结点的 next 指针指向链表 $ h_1 $ 的头结点，形成循环结构。

代码实现

以下是 C++ 代码示例，用于实现上述算法：

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
#include <iostream>
using namespace std;

struct LNode {
    int data;          // 数据域
    LNode *next;      // 指针域
};

typedef LNode* LinkList;

// 将循环链表 h2 链接到循环链表 h1 之后
LinkList Link(LinkList &h1, LinkList &h2) {
    // 若 h1 或 h2 为空，直接返回 h1
    if (h1 == nullptr) return h2;
    if (h2 == nullptr) return h1;

    // 找到 h1 的尾结点
    LNode *p = h1;
    while (p->next != h1) {
        p = p->next; // 找到 h1 的尾结点
    }

    // 找到 h2 的尾结点
    LNode *q = h2;
    while (q->next != h2) {
        q = q->next; // 找到 h2 的尾结点
    }

    // 将 h1 的尾结点链接到 h2 的头结点
    p->next = h2; // h1 的尾指针指向 h2 的头指针
    // 将 h2 的尾结点链接到 h1 的头结点
    q->next = h1; // h2 的尾指针指向 h1 的头指针

    return h1; // 返回链接后的链表头指针
}

// 辅助函数：创建循环链表
LinkList CreateCircularList(int arr[], int n) {
    if (n == 0) return nullptr;
    
    LinkList head = new LNode{arr[0], nullptr}; // 创建头结点
    LNode *tail = head; // 尾指针
    for (int i = 1; i < n; ++i) {
        LNode *newNode = new LNode{arr[i], nullptr};
        tail->next = newNode; // 在链表尾部插入新结点
        tail = newNode;       // 更新尾指针
    }
    tail->next = head; // 尾结点指向头结点，形成循环
    return head;
}

// 辅助函数：打印循环链表
void PrintCircularList(LinkList head) {
    if (head == nullptr) return;

    LNode *p = head;
    do {
        cout << p->data << " ";
        p = p->next;
    } while (p != head);
    cout << endl;
}

// 主函数示例
int main() {
    int arr1[] = {1, 2, 3}; // 链表 h1
    int arr2[] = {4, 5};    // 链表 h2

    LinkList h1 = CreateCircularList(arr1, 3); // 创建循环链表 h1
    LinkList h2 = CreateCircularList(arr2, 2); // 创建循环链表 h2

    cout << "链表 h1: ";
    PrintCircularList(h1); // 打印链表 h1

    cout << "链表 h2: ";
    PrintCircularList(h2); // 打印链表 h2

    Link(h1, h2); // 将 h2 链接到 h1 后

    cout << "链接后的链表 h1: ";
    PrintCircularList(h1); // 打印链接后的链表

    // 释放链表内存
    LNode *p = h1;
    if (p != nullptr) {
        LNode *temp;
        do {
            temp = p;
            p = p->next;
            delete temp; // 逐个释放链表 h1 的结点
        } while (p != h1);
    }

    return 0;
}

代码说明

  • Link 函数：该函数负责将循环链表 $ h_2 $ 链接到循环链表 $ h_1 $ 的后面，并保持循环结构。

  • 辅助函数：CreateCircularList 用于创建循环链表，PrintCircularList 用于打印链表的元素。

时间与空间复杂度

  • 时间复杂度：$ O(m + n) $，其中 $ m $ 是链表 $ h_1 $ 的长度，$ n $ 是链表 $ h_2 $ 的长度，因为需要遍历两个链表。

  • 空间复杂度：$ O(1) $，只使用了常量级的额外空间。

示例输出

运行该代码，输出将为：

1
2
3
链表 h1: 1 2 3 
链表 h2: 4 5 
链接后的链表 h1: 1 2 3 4 5

问题18:设有一个带头结点的循环单链表，其节点值均为正整数。设计一个算法，反复找出单链表中节点值最小的节点并输出，然后将该节点从中删除，直到单链表为空为止，最后删除表头节点。

解答

算法思想

  1. 使用两个指针 p 和 pre 遍历循环单链表，p 用于指向当前节点，pre 用于指向 p 的前驱节点。
  2. 在每次循环中，找出最小值节点 minp 和它的前驱节点 minpre。
  3. 找到最小节点后，将其从链表中删除，并输出该节点的值。
  4. 重复上述步骤，直到链表为空。
  5. 最后释放头结点。

代码实现

以下是 C++ 代码示例，用于实现上述算法：

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
#include <iostream>
using namespace std;

struct LNode {
    int data;          // 数据域
    LNode *next;      // 指针域
};

typedef LNode* LinkList;

// 删除循环单链表中的所有最小值节点
void DelAll(LinkList &L) {
    LNode *p, *pre, *minp, *minpre;

    // 检查链表是否为空
    while (L->next != L) { // 表不空，循环
        p = L->next; // p为工作指针，指向链表第一个元素
        pre = L;     // pre指向头结点

        // 初始化最小值指针
        minp = p;
        minpre = pre;

        // 循环一趟，查找最小值结点
        while (p != L) { // 遍历整个链表
            if (p->data < minp->data) { // 找到更小的结点
                minp = p;
                minpre = pre; // 更新前驱结点
            }
            pre = p;         // 更新前驱
            p = p->next;    // 访问下一个结点
        }

        // 输出最小值结点元素
        cout << "最小值结点: " << minp->data << endl;

        // 从链表中断开最小值结点
        minpre->next = minp->next; // 删除 minp 结点
        free(minp); // 释放空间
    }

    // 释放头结点
    free(L);
}

// 辅助函数：创建循环单链表
LinkList CreateCircularList(int arr[], int n) {
    if (n == 0) return nullptr;

    LinkList head = new LNode{0, nullptr}; // 创建头结点
    LNode *tail = head; // 尾指针
    for (int i = 0; i < n; ++i) {
        LNode *newNode = new LNode{arr[i], nullptr};
        tail->next = newNode; // 在链表尾部插入新结点
        tail = newNode;       // 更新尾指针
    }
    tail->next = head; // 尾结点指向头结点，形成循环
    return head;
}

// 主函数示例
int main() {
    int arr[] = {3, 1, 4, 1, 5, 9, 2}; // 示例数据
    LinkList L = CreateCircularList(arr, 7); // 创建循环链表

    cout << "删除循环链表中的所有最小值结点:" << endl;
    DelAll(L); // 删除并输出最小值结点

    return 0;
}

代码说明

  • DelAll 函数：该函数实现每次删除循环单链表中的最小元素，直到链表为空。使用指针 minp 和 minpre 找到最小值节点及其前驱节点，并在找到后将其从链表中删除。
  • 辅助函数：CreateCircularList 用于创建循环单链表。

时间与空间复杂度

  • 时间复杂度：$ O(n^2) $，每次删除最小节点时需要遍历链表一次，重复此操作直到链表为空。
  • 空间复杂度：$ O(1) $，只使用了常量级的额外空间。

示例输出

运行该代码，输出将为：

1
2
3
4
5
6
7
8
删除循环链表中的所有最小值结点:
最小值结点: 1
最小值结点: 1
最小值结点: 2
最小值结点: 3
最小值结点: 4
最小值结点: 5
最小值结点: 9

问题19:

设头指针为 L 的带有表头结点的非循环双向链表，其每个节点中除了有 pred（前驱指针）、data（数据）和 next（后继指针）域外，还有一个访问频度域 freq。在链表被启用前，freq 值均初始化为零。

每当在链表中进行一次 Locate(L, x) 运算时：

  1. 令元素值为 x 的节点中 freq 域的值增 1。
  2. 使此链表中的节点保持按访问频度非增（递减）的顺序排列，同时最近访问的节点排在频度相同的节点前面。

请编写符合上述要求的 Locate(L, x) 运算的算法，该运算为函数过程，返回找到节点的地址，类型为指针型。

解答

算法思想

  1. 首先，在双向链表中查找数据值为 x 的节点。
  2. 如果找到该节点，将其摘下（从链表中删除）。
  3. 增加该节点的 freq 值。
  4. 在链表中查找该节点的新插入位置，保持按频度递减排序，且同频度节点按最近访问顺序排列。
  5. 将节点插入到找到的位置。

代码实现

以下是 C++ 代码示例，用于实现上述算法：

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
#include <iostream>
using namespace std;

struct DNode {
    int data;          // 数据域
    DNode *pred;      // 前驱指针
    DNode *next;      // 后继指针
    int freq;         // 访问频度
};

typedef DNode* DLinkList; // 定义双向链表类型

// 在双向链表中查找并插入
DLinkList Locate(DLinkList &L, int x) {
    DNode *p = L->next; // 从头结点开始
    DNode *q;           // 用于插入位置的指针

    // 查找值为x的结点
    while (p != nullptr && p->data != x) {
        p = p->next;
    }

    if (p == nullptr) {
        cout << "节点值为 " << x << " 的结点不存在。" << endl;
        exit(0); // 不存在值为x的结点，退出
    }

    // 增加频度
    p->freq++;

    // 如果p是链表首结点，或者freq值小于前驱结点，直接返回
    if (p->pred == L || p->pred->freq > p->freq) {
        return p;
    }

    // 将p结点从链表上摘下
    if (p->next != nullptr) {
        p->next->pred = p->pred;
    }
    p->pred->next = p->next;

    // 查找插入位置
    q = p->pred; // 从p的前驱开始查找
    while (q != L && q->freq <= p->freq) {
        q = q->pred; // 找到第一个比p频度大的结点
    }

    // 插入p结点到链表
    p->next = q->next; // p的后继指向q的后继
    if (q->next != nullptr) {
        q->next->pred = p; // 更新q后继的前驱
    }
    p->pred = q; // p的前驱指向q
    q->next = p; // q的后继指向p

    return p; // 返回找到的节点
}

// 辅助函数：创建双向链表
DLinkList CreateDoublyLinkedList(int arr[], int n) {
    if (n == 0) return nullptr;

    DLinkList head = new DNode{0, nullptr, nullptr, 0}; // 创建头结点
    DNode *tail = head; // 尾指针
    for (int i = 0; i < n; ++i) {
        DNode *newNode = new DNode{arr[i], tail, nullptr, 0};
        tail->next = newNode; // 在链表尾部插入新结点
        tail = newNode;       // 更新尾指针
    }
    tail->next = nullptr; // 设置尾结点的后继为nullptr
    return head;
}

// 主函数示例
int main() {
    int arr[] = {5, 3, 8, 1, 7}; // 示例数据
    DLinkList L = CreateDoublyLinkedList(arr, 5); // 创建双向链表

    int x = 3; // 要查找的节点值
    DNode *result = Locate(L, x); // 查找并重排
    cout << "找到节点值 " << result->data << "，频度为 " << result->freq << endl;

    // 输出链表节点
    DNode *temp = L->next;
    cout << "链表节点值及频度: " << endl;
    while (temp != nullptr) {
        cout << "节点值: " << temp->data << ", 频度: " << temp->freq << endl;
        temp = temp->next;
    }

    return 0;
}

代码说明

  • Locate 函数：该函数在双向链表中查找值为 x 的节点，并在频度更新后重新插入到正确位置。
  • 辅助函数：CreateDoublyLinkedList 用于创建一个带有头结点的双向链表。

时间与空间复杂度

  • 时间复杂度：最坏情况下为 $O(n)$，因为需要遍历整个链表。
  • 空间复杂度：$O(1)$，只使用了常量级的额外空间。

示例输出

运行该代码，输出将为：

1
2
3
4
5
6
7
找到节点值 3，频度为 1
链表节点值及频度: 
节点值: 5, 频度: 0
节点值: 3, 频度: 1
节点值: 8, 频度: 0
节点值: 1, 频度: 0
节点值: 7, 频度: 0

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

1) 基本设计思想

要判断单链表是否存在环，常用的算法是 快慢指针法（也称为 Floyd 判圈算法）。基本思想是使用两个指针，slow 和 fast，从链表的头结点开始遍历：

  • slow 每次移动一步。
  • fast 每次移动两步。

如果链表中存在环，slow 和 fast 指针最终会相遇；如果链表没有环，fast 指针将会到达链表的末尾（即 nullptr）。

2) C++ 代码实现

以下是用 C++ 实现判断单链表是否存在环的算法：

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
#include <iostream>

struct Node {
    int data;      // 数据域
    Node* next;    // 指向下一个节点的指针
};

// 判断单链表是否存在环的函数
bool hasCycle(Node* head) {
    if (head == nullptr) return false; // 空链表无环

    Node* slow = head; // 慢指针
    Node* fast = head; // 快指针

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;         // 慢指针每次走一步
        fast = fast->next->next;   // 快指针每次走两步

        if (slow == fast) { // 如果两指针相遇，说明存在环
            return true;
        }
    }

    return false; // 遍历结束未相遇，说明无环
}

// 主函数示例
int main() {
    // 创建一个单链表，示例：1 -> 2 -> 3 -> 4 -> 2（形成环）
    Node* head = new Node{1, nullptr};
    head->next = new Node{2, nullptr};
    head->next->next = new Node{3, nullptr};
    head->next->next->next = new Node{4, nullptr};
    head->next->next->next->next = head->next; // 创建环

    // 判断是否存在环
    if (hasCycle(head)) {
        std::cout << "链表中存在环。" << std::endl;
    } else {
        std::cout << "链表中不存在环。" << std::endl;
    }

    // 释放链表（注意，环的释放需要特殊处理）
    // 此处省略释放代码，实际中应处理环释放

    return 0;
}

3) 时间复杂度和空间复杂度

  • 时间复杂度：$O(n)$，其中 $n$ 是链表的长度。在最坏情况下，两个指针可能需要遍历链表的所有节点才能确定链表是否存在环。

  • 空间复杂度：$O(1)$，只使用了常量级的额外空间，两个指针 slow 和 fast。

问题21:给定一个带有表头结点的单链表，要求查找链表中倒数第 $ k $ 个位置上的结点，并返回该结点的 data 域的值。若查找成功，输出该结点的 data 域的值并返回 1；若失败，返回 0。

1) 算法的基本设计思想

要查找链表中倒数第 $ k $ 个结点，我们可以使用 双指针法。具体步骤如下：

  1. 定义两个指针 p 和 q，初始都指向链表的第一个实际结点（头结点的下一个结点）。
  2. 移动指针 p 使其先走 $ k $ 步。
  3. 然后同时移动 p 和 q，直到 p 到达链表的末尾。
  4. 当 p 到达末尾时，q 就会指向倒数第 $ k $ 个结点。

该方法只需遍历链表一次，因此时间复杂度为 $ O(n) $，空间复杂度为 $ O(1) $。

2) 算法的详细实现步骤

  1. 初始化：将 count 设为 0，指针 p 和 q 都指向链表头结点的下一个结点。
  2. 检查空链表：如果 p 为 NULL，返回 0（链表为空）。
  3. 移动指针 p：
    • 每次移动 p 指向下一个结点。
    • 如果 count 小于 $ k $，则将 count 加 1。
    • 否则，将 q 移动到下一个结点。
  4. 完成遍历：当 p 到达链表末尾时，检查 count 是否小于 $ k $。
    • 如果是，返回 0（链表长度小于 $ k $）。
    • 否则，输出 q 的 data 值并返回 1。

3) C++ 实现

以下是用 C++ 实现该算法的代码：

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
#include <iostream>

struct LNode {
    int data;           // 数据域
    LNode* link;       // 指向下一个节点的指针
};

typedef LNode* LinkList;

// 查找链表中倒数第k个节点的函数
int SearchK(LinkList list, int k) {
    LNode* p = list->link;  // p指向第一个实际节点
    LNode* q = list->link;  // q指向第一个实际节点
    int count = 0;

    // 移动p指针，直到其遍历到链表末尾
    while (p != nullptr) {
        if (count < k) {
            count++; // 计数增加
        } else {
            q = q->link; // 移动q指针
        }
        p = p->link; // p指针向前移动
    }

    // 检查是否成功找到倒数第k个节点
    if (count < k) {
        return 0; // 查找失败，返回0
    } else {
        std::cout << q->data << std::endl; // 输出q指向节点的data值
        return 1; // 查找成功，返回1
    }
}

// 主函数示例
int main() {
    // 创建示例链表，添加节点
    LinkList list = new LNode{0, nullptr}; // 头结点
    list->link = new LNode{1, nullptr};
    list->link->link = new LNode{2, nullptr};
    list->link->link->link = new LNode{3, nullptr};
    list->link->link->link->link = new LNode{4, nullptr};

    // 查找倒数第k个节点
    int k = 2; // 例：查找倒数第2个节点
    int result = SearchK(list, k);
    if (result == 0) {
        std::cout << "链表中不存在倒数第 " << k << " 个节点。" << std::endl;
    }

    // 释放链表（注意，需循环释放所有节点）
    // 此处省略释放代码

    return 0;
}

总结

  • 时间复杂度：$ O(n) $，遍历链表一次。
  • 空间复杂度：$ O(1) $，只使用了常量级的额外空间。

问题22:给定两个带头结点的单链表 str1 和 str2，当两个单词有相同的后缀时，可以共享相同的后缀存储空间。设计一个算法找出两个链表共同后缀的起始位置。

1) 算法的基本设计思想

  1. 计算链表长度：分别计算链表 str1 和 str2 的长度 $ m $ 和 $ n $。
  2. 调整指针：令指针 p 和 q 分别指向 str1 和 str2 的头结点。
    • 如果 $ m > n $，则让 p 先移动 $ m - n $ 步，使得 p 和 q 到达的后缀长度相等。
    • 如果 $ m < n $，则让 q 先移动 $ n - m $ 步。
  3. 同步移动指针：同时移动指针 p 和 q，直到找到相同的位置，即为共同后缀的起始位置。

2) 算法的详细实现步骤

  1. 定义链表节点结构：

    1
    2
    3
    4
    typedef struct Node {
        char data;               // 字符数据
        struct Node* next;      // 指向下一个节点的指针
    } Node;

  2. 计算链表长度的函数：

    1
    2
    3
    4
    5
    6
    7
    8
    int listlen(Node* head) {
        int len = 0;
        while (head->next != NULL) {
            len++;
            head = head->next; // 移动到下一个节点
        }
        return len; // 返回链表的长度
    }

  3. 寻找共同后缀的起始地址的函数：

    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
    Node* findAddr(Node* str1, Node* str2) {
        int m = listlen(str1); // 求 str1 的长度
        int n = listlen(str2); // 求 str2 的长度
        Node* p = str1->next;  // p 指向 str1 的第一个实际节点
        Node* q = str2->next;  // q 指向 str2 的第一个实际节点

        // 使 p 和 q 对齐，使它们到链表尾部的长度相等
        if (m > n) {
            for (int i = 0; i < (m - n); i++) {
                p = p->next; // p 先走 m - n 步
            }
        } else {
            for (int i = 0; i < (n - m); i++) {
                q = q->next; // q 先走 n - m 步
            }
        }

        // 同时移动 p 和 q，直到找到相同的节点
        while (p != NULL && q != NULL) {
            if (p == q) {
                return p; // 返回共同后缀的起始节点
            }
            p = p->next;
            q = q->next;
        }

        return NULL; // 没有找到共同后缀，返回 NULL
    }

3) 时间复杂度分析

  • 时间复杂度：$ O(m + n) $，其中 $ m $ 和 $ n $ 分别为链表 str1 和 str2 的长度。因为我们分别遍历了两个链表来计算长度，并再次遍历到找到共同后缀的起始位置。
  • 空间复杂度：$ O(1) $，只使用了常量级的额外空间。

问题23:设计一个算法，对于用单链表保存的 $ m $ 个整数，删除链表中绝对值相等的节点，仅保留第一次出现的节点。

1) 算法的基本设计思想

算法的核心思想是使用辅助数组来记录链表中已经出现的绝对值，利用空间换取时间，以便在一次遍历中完成对链表的处理：

  1. 辅助数组：使用一个大小为 $ n + 1 $ 的辅助数组 q（假设绝对值不超过 $ n $），数组初值为 0，用于标记每个整数的绝对值是否已出现。
  2. 遍历链表：依次遍历链表中的每个节点，检查该节点的绝对值在数组 q 中的状态：
    • 如果 q[m]（当前节点的绝对值）为 0，表示该绝对值第一次出现，保留该节点，并将 q[m] 设置为 1。
    • 如果 q[m] 不为 0，表示该绝对值已经出现过，删除该节点。

2) 单链表节点的数据类型定义（C语言）

1
2
3
4
5
6
typedef struct node {
    int data;                // 节点数据
    struct node* link;      // 指向下一个节点的指针
} NODE;

typedef NODE* PNODE;        // 定义 PNODE 为 NODE 的指针类型

3) 算法实现

以下是实现该算法的 C 语言代码：

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
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;                // 节点数据
    struct node* link;      // 指向下一个节点的指针
} NODE;

typedef NODE* PNODE;        // 定义 PNODE 为 NODE 的指针类型

void func(PNODE head, int n) {
    PNODE p = head, r;      // p 用于遍历链表
    int *q;                 // 辅助数组
    q = (int *)malloc(sizeof(int) * (n + 1)); // 申请辅助空间
    // 初始化辅助数组
    for (int i = 0; i <= n; i++) {
        q[i] = 0;           // 设置初值为 0
    }

    // 遍历链表，进行删除操作
    while (p->link != NULL) {
        int m = abs(p->link->data); // 获取当前节点的绝对值
        // 判断该绝对值是否已出现过
        if (q[m] == 0) {
            // 首次出现，保留该节点
            q[m] = 1;             // 标记为已出现
            p = p->link;         // 移动到下一个节点
        } else {
            // 重复出现，删除该节点
            r = p->link;          // r 指向当前节点
            p->link = r->link;   // 删除 r 节点
            free(r);             // 释放内存
        }
    }
    free(q);                    // 释放辅助数组的内存
}

4) 时间复杂度和空间复杂度分析

  • 时间复杂度：$ O(m) $，其中 $ m $ 是链表中的节点数量。我们只需遍历链表一次。
  • 空间复杂度：$ O(n) $，其中 $ n $ 是节点数据的绝对值的最大值。我们使用了一个大小为 $ n + 1 $ 的辅助数组。

问题24:设线性表 $ L = (a_1, a_2, \ldots, a_n) $ 采用带头结点的单链表保存，要求设计一个空间复杂度为 $ O(1) $ 且时间上尽可能高效的算法，将链表中的各节点重新排列为 $ L’ = (a_1, a_n, a_2, a_{n-1}, a_3, a_{n-2}, \ldots) $。

1) 算法的基本设计思想

根据给定的线性表 $ L $ 和目标线性表 $ L’ $，我们可以观察到 $ L’ $ 的形成是通过依次摘取前面的元素和后面的元素来实现的。为了高效地实现这一目标，采用以下步骤：

  1. 找中间节点：使用快慢指针法找到链表的中间节点，慢指针每次走一步，快指针每次走两步。
  2. 逆置后半段链表：将链表的后半部分原地逆置，方便后续交替取节点。
  3. 合并前后两段：依次从前半段和逆置后的后半段中取节点，重新排列成所需的形式。

2) 算法实现（C语言）

以下是实现该算法的 C 语言代码：

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
#include <stdio.h>
#include <stdlib.h>

// 定义单链表节点结构
typedef struct node {
    int data;                  // 节点数据
    struct node* next;        // 指向下一个节点的指针
} NODE;

void change_list(NODE* head) {
    NODE *p, *q, *r, *s;

    p = head;                  // 指向头结点
    q = head;                  // 指向头结点

    // 第一步：寻找中间结点
    while (q->next != NULL) {
        p = p->next;          // p 走一步
        q = q->next;         
        if (q->next != NULL)  // q 走两步
            q = q->next;
    }

    // p 现在指向中间结点，q 为后半段链表的首结点
    q = p->next;              // q 指向后半段的起始节点
    p->next = NULL;           // 断开前后两段

    // 第二步：逆置后半段链表
    NODE* prev = NULL;        // 记录前一个节点
    while (q != NULL) {
        r = q->next;          // 保存下一个节点
        q->next = prev;       // 逆置指针
        prev = q;             // 移动 prev
        q = r;                // 移动 q
    }

    // 现在 prev 指向后半段链表的头结点

    // 第三步：合并前后两段
    p = head->next;           // p 指向前半段的第一个数据结点
    s = head;                 // s 指向头结点
    q = prev;                 // q 指向后半段的第一个数据结点

    while (q != NULL) {
        // 将后半段的节点插入到前半段中
        r = q->next;          // 保存后半段的下一个节点
        q->next = p;          // 插入到前半段后
        p = p->next;          // 移动前半段指针
        s->next = q;          // 更新头结点的 next
        s = s->next;          // 移动到下一个位置
        q = r;                // 移动到下一个后半段节点
    }
}

int main() {
    // 代码示例：构造链表并调用 change_list 函数
    NODE* head = (NODE*)malloc(sizeof(NODE));
    head->next = NULL;

    // 在这里添加代码以构造示例链表

    change_list(head);        // 调用重排函数

    // 在这里添加代码以打印重排后的链表

    return 0;
}

3) 时间复杂度分析

  • 时间复杂度：整个算法的时间复杂度为 $ O(n) $，其中 $ n $ 是链表中的节点数量。我们分别进行了链表遍历（找中间节点）、逆置（重新排列）和合并（重新构造链表）的操作，均为线性复杂度。
  • 空间复杂度：算法的空间复杂度为 $ O(1) $，因为我们只使用了常量级的额外空间（指针变量）。

问题25:给定一个长度为 $ N $ 的整型数组 $ A[1..N] $ 和一个整数 $ X $，设计一个时间复杂度不超过 $ O(n \log n) $ 的算法，查找出这个数组中所有两两之和等于 $ X $ 的整数对（每个元素只输出一次）。

解决方案

方法一：排序 + 双指针

如提示中所述，可以先对数组进行排序，然后使用双指针法来查找满足条件的整数对。以下是具体步骤：

  1. 排序：使用快速排序或归并排序等 $ O(n \log n) $ 的排序算法将数组 $ A $ 从小到大排序。
  2. 双指针查找：设置两个指针，分别指向数组的开始和结束。根据两个指针指向的元素的和与 $ X $ 的关系来移动指针：
    • 如果 $ A[i] + A[j] < X $，则移动左指针 $ i $（即增大 $ A[i] $）。
    • 如果 $ A[i] + A[j] > X $，则移动右指针 $ j $（即减小 $ A[j] $）。
    • 如果 $ A[i] + A[j] = X $，则输出 $ A[i] $ 和 $ A[j] $，然后同时移动两个指针。

算法实现

以下是实现该算法的 C 语言代码示例：

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
#include <stdio.h>
#include <stdlib.h>

// 比较函数用于快速排序
int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

void find_pairs(int* A, int N, int X) {
    // Step 1: 对数组进行排序
    qsort(A, N, sizeof(int), compare);
    
    int i = 0;                  // 从头开始
    int j = N - 1;              // 从尾开始
    
    while (i < j) {
        int sum = A[i] + A[j];
        if (sum < X) {
            i++;                // 增加小端指针
        } else if (sum > X) {
            j--;                // 减少大端指针
        } else {
            printf("Pair found: (%d, %d)\n", A[i], A[j]);
            i++;                // 移动指针，避免重复
            j--;
        }
    }
}

int main() {
    int A[] = {1, 2, 3, 4, 5, 6};
    int N = sizeof(A) / sizeof(A[0]);
    int X = 7;

    find_pairs(A, N, X);      // 查找和为 X 的整数对

    return 0;
}

时间复杂度分析

  • 排序的时间复杂度：使用 $ O(n \log n) $ 的排序算法（如快速排序）。
  • 双指针查找的时间复杂度：在最坏情况下，每个指针最多遍历一次整个数组，因此时间复杂度为 $ O(n) $。
  • 整体时间复杂度：算法的整体时间复杂度为 $ O(n \log n) $。

方法二：哈希表

除了上述方法外，还可以使用哈希表来解决该问题。具体步骤如下：

  1. 遍历数组，将所有元素存入哈希表中，记录出现的次数。
  2. 再次遍历数组，检查每个元素 $ a $ 是否存在 $ X - a $。
    • 如果存在且没有输出过，则输出这一对。
    • 更新哈希表以避免重复输出。

哈希表实现示例

以下是使用哈希表实现的 C 语言代码示例：

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
#include <stdio.h>
#include <stdlib.h>

typedef struct HashNode {
    int key;
    struct HashNode* next;
} HashNode;

typedef struct HashTable {
    HashNode** table;
    int size;
} HashTable;

// 创建哈希表
HashTable* create_table(int size) {
    HashTable* ht = (HashTable*)malloc(sizeof(HashTable));
    ht->size = size;
    ht->table = (HashNode**)malloc(size * sizeof(HashNode*));
    for (int i = 0; i < size; i++) {
        ht->table[i] = NULL;
    }
    return ht;
}

// 哈希函数
int hash(int key, int size) {
    return key % size;
}

// 插入到哈希表
void insert(HashTable* ht, int key) {
    int index = hash(key, ht->size);
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    newNode->key = key;
    newNode->next = ht->table[index];
    ht->table[index] = newNode;
}

// 查找元素
int search(HashTable* ht, int key) {
    int index = hash(key, ht->size);
    HashNode* node = ht->table[index];
    while (node != NULL) {
        if (node->key == key) {
            return 1; // 找到
        }
        node = node->next;
    }
    return 0; // 未找到
}

// 释放哈希表
void free_table(HashTable* ht) {
    for (int i = 0; i < ht->size; i++) {
        HashNode* node = ht->table[i];
        while (node != NULL) {
            HashNode* temp = node;
            node = node->next;
            free(temp);
        }
    }
    free(ht->table);
    free(ht);
}

// 使用哈希表查找和为 X 的整数对
void find_pairs_with_hash(int* A, int N, int X) {
    HashTable* ht = create_table(N * 2); // 创建哈希表，大小为 2N
    for (int i = 0; i < N; i++) {
        insert(ht, A[i]); // 将每个元素插入哈希表
    }

    for (int i = 0; i < N; i++) {
        int complement = X - A[i];
        if (search(ht, complement)) {
            printf("Pair found: (%d, %d)\n", A[i], complement);
        }
    }
    free_table(ht); // 释放哈希表
}

int main() {
    int A[] = {1, 2, 3, 4, 5, 6};
    int N = sizeof(A) / sizeof(A[0]);
    int X = 7;

    find_pairs_with_hash(A, N, X); // 查找和为 X 的整数对

    return 0;
}

时间复杂度分析

  • 构建哈希表的时间复杂度：为 $ O(n) $，遍历数组并插入每个元素。
  • 查找和的时间复杂度：对于每个元素查找其补数，平均时间复杂度为 $ O(1) $。
  • 整体时间复杂度：总时间复杂度为 $ O(n) + O(n) = O(n) $。
  • 空间复杂度：使用了额外的哈希表，空间复杂度为 $ O(n) $。