本文共 4753 字，大约阅读时间需要 15 分钟。

链表的各种题目整理(C语言实现)

最后更新于：2023-10-04

---

链表的各种题目整理

以下内容将围绕单链表的各种常见操作进行详细介绍，包括实现代码和测试案例。

---

链表长度计算

问题描述：

计算链表的长度。

算法：

使用一个计数器从头结点开始遍历链表，直到遇到 NULL 结点。计数器加一。

复杂度：

O(n)，其中 n 为链表的长度。

代码实现：

int list_len(node_t *head) {    int i = 0;    for (; head; head = head->next, i++) {        ;    }    return i;}

测试案例：

node_t d = {"d", 0}, c = {"c", &d}, b = {"b", &c}, a = {"a", &b};printf("%d\n", list_len(&a)); // 输出：4

---

反转链表

问题描述：

将链表反转。

算法：

使用三个指针 p、q 和 t。

• t 遍历链表，记录当前结点。
• q 记录 t 的前一个结点。
• p 用于缓存 t 的值。

代码实现：

void reverse(node_t *head) {    node_t *p = 0, *q = 0, *t = 0;    for (t = head; t; p = t, t = t->next, p->next = q, q = p) {        ;    }}

测试案例：

node_t d = {"d", 0}, c = {"c", &d}, b = {"b", &c}, a = {"a", &b};list_display(&a);reverse(&a);list_display(&d); // 链表已反转

---

查找倒数第k个元素

问题描述：

找到链表中倒数第k个元素（尾结点为倒数第0个）。

算法：

• 使用两个指针 p 和 q，初始都指向头结点。
• p 先跑 k 个结点，q 跑剩下的。
• 当 p 到达尾结点时，q 正好位于倒数第k个元素。

代码实现：

node_t *_kth(node_t *head, int k) {    int i = 0;    node_t *p = head, *q = head;    for (; p && i < k; p = p->next, i++) {        ;    }    if (i < k) return 0;    for (; p->next; p = p->next, q = q->next) {        ;    }    return q;}

测试案例：

node_t d = {"d", 0}, c = {"c", &d}, b = {"b", &c}, a = {"a", &b};printf("_0 :%s _1: %s _2:%s _3:%s\n",       _kth(&a, 0)->data, _kth(&a, 1)->data, _kth(&a, 2)->data, _kth(&a, 3)->data);

---

查找中间结点

问题描述：

找到链表的中间结点。

算法：

• 使用两个指针 p 和 q，p 跑两步，q 跑一步。
• 当 p 到达尾结点时，q 即为中间结点。

代码实现：

node_t *middle(node_t *head) {    node_t *p, *q;    for (p = q = head; p->next; p = p->next, q = q->next) {        p = p->next;        if (!p) break;    }    return q;}

测试案例：

node_t e = {"e", 0}, d = {"d", &e}, c = {"c", &d}, b = {"b", &c}, a = {"a", &b};printf("%s\n", middle(&a)->data);

---

逆序打印链表

问题描述：

逆序打印链表。

算法：

使用递归，逆序遍历链表。

代码实现：

void r_display(node_t *t) {    if (t) {        r_display(t->next);        printf("%s", t->data);    }}

---

判断链表是否有环

问题描述：

判断一个链表是否存在环。

算法：

• 使用两个指针 p 和 q，p 跑得快，q 跑得慢。
• 如果 p 和 q 相遇，说明链表有环。

代码实现：

int any_ring(node_t *head) {    node_t *p, *q;    for (p = q = head; p; p = p->next, q = q->next) {        p = p->next;        if (!p) break;        if (p == q) return 1; // 存在环    }    return 0; // 无环}

测试案例：

node_t e = {"e", 0}, d = {"d", &e}, c = {"c", &d}, b = {"b", &c}, a = {"a", &b};e->next = &d; // 创建环printf("%d\n", any_ring(&a)); // 输出：1

---

找出环的入口结点

问题描述：

找到链表中环的入口结点。

算法：

• 使用三个指针 p、q 和 r。
• p 和 q 相遇时，r 从头结点开始，逐步追赶，找到环的入口。

代码实现：

node_t *find_entry(node_t *head) {    node_t *p, *q, *r;    for (p = q = r = head; p; p = p->next, q = q->next) {        p = p->next;        if (!p) break;        if (p == q) break;    }    if (!p) return 0; // 无环    for (r = head, q = q->next; q != r; r = r->next, q = q->next) {        ;    }    return r;}

测试案例：

node_t e = {"e", 0}, d = {"d", &e}, c = {"c", &d}, b = {"b", &c}, a = {"a", &b};e->next = &d; // 创建环printf("%s\n", find_entry(&a)->data); // 输出："a"

---

判断两个链表是否相交

问题描述：

判断两个链表是否相交。

算法：

• 使用两个指针分别遍历两个链表，比较尾结点。如果尾结点相同，则相交。

代码实现：

int is_intersect(node_t *a, node_t *b) {    if (!a || !b) return -1; // 头指针为空    for (; a->next; a = a->next);    for (; b->next; b = b->next);    return a == b ? 1 : 0; // 1 表示相交，0 表示不相交}

测试案例：

node_t e = {"e", 0}, d = {"d", &e}, c = {"c", &d}, b = {"b", &c}, a = {"a", &b};node_t z = {"z", &c}, y = {"y", &z}, x = {"x", &y};printf("%d\n", is_intersect(&a, &x)); // 输出：1

---

找两个链表相交的交点

问题描述：

找到两个链表相交的交点。

算法：

• 分别用两个指针遍历两个链表，找到哪个链表先到达尾结点。
• 从第一个链表的头结点开始，逐步追赶第二个链表的指针，直到相遇。

代码实现：

node_t *intersect_point(node_t *a, node_t *b) {    node_t *p, *q, *k, *t, *s;    for (p = a, q = b; p && q; p = p->next, q = q->next) {        k = (p == 0) ? q : p;        t = (p == 0) ? b : a;        s = (p == 0) ? a : b;    }    for (; k; k = k->next, t = t->next) {        ;    }    for (; t != s; t = t->next, s = s->next) {        ;    }    return t;}

测试案例：

node_t e = {"e", 0}, d = {"d", &e}, c = {"c", &d}, b = {"b", &c}, a = {"a", &b};node_t z = {"z", &b}, y = {"y", &z}, x = {"x", &y};printf("%s\n", intersect_point(&a, &x)->data); // 输出："y"

---

O(1) 删除结点（不给头结点）

问题描述：

在不给头结点的情况下，删除链表中的一个结点。

算法：

将需要删除的结点的下一个结点的数据复制到该结点中，然后删除下一个结点。

代码实现：

node_t *delete(node_t *d) {    node_t *e = d->next;    d->data = e->data;    d->next = e->next;    return d;}

---

两个链表右对齐打印

问题描述：

两个链表右对齐打印。

算法：

• 遍历两个链表，找到较短链表的尾部。
• 从头结点开始，逐个打印较长链表的结点，间隔适当空格。

代码实现：

void foo(node_t *a, node_t *b) {    node_t *p, *q, *k, *t, *s;    for (p = a, q = b; p && q; p = p->next, q = q->next) {        k = p ? p : q;        t = p ? a : b;        s = p ? b : a;    }    for (; t; printf("%d ", t->data), t = t->next);    printf("\n");    for (; k; printf("    "), k = k->next);    for (; s; printf("%d ", s->data), s = s->next);}

测试案例：

node_t e = {5, 0}, d = {4, &e}, c = {3, &d}, b = {2, &c}, a = {1, &b};node_t o = {8, 0}, n = {7, &o}, m = {6, &n};foo(&a, &m); // 输出：1 2 3 4 5     6 7 8

---

以上是关于单链表操作的常见问题及解决方案，涵盖了长度计算、反转、查找特定元素、中间结点、逆序打印、环检测、交点查找等多个主题。

转载地址：http://lwuk.baihongyu.com/