qidao123.com技术社区-IT企服评测·应用市场

标题: 数据结构逐日一题day14（链表）★★★★★ [打印本页]

---

作者: 丝    时间: 2025-5-8 03:16
标题: 数据结构逐日一题day14（链表）★★★★★
标题描述：试编写算法将带头结点的单链表就地逆置，所谓“就地”就是空间复杂度为O（1)。

算法思想：

1.初始化：
定义三个指针 prev、curr、next，分别表示前驱节点、当前节点和后继节点。
prev 初始化为 NULL，curr 初始化为头结点的下一个节点（即第一个有效节点）。
2.遍历链表并反转：
遍历链表，每次将 curr->next 指向 prev，实现局部反转。
然后 prev、curr、next 依次后移，继续处理下一个节点。
3.修正头结点指针：
遍历结束后，prev 指向原链表的最后一个节点，即新链表的第一个节点。
将头结点的 next 指向 prev，完成整个链表的逆置。

复杂度分析：
时间复杂度：O(n)
空间复杂度：O(1)

代码实现：

1. #include <stdio.h>
2. #include <stdlib.h>
4. typedef struct Node {
5.     int data;
6.     struct Node *next;
7. } Node, *LinkedList;
9. // 创建链表（尾插法）
10. LinkedList createList() {
11.     LinkedList L = (Node*)malloc(sizeof(Node)), tail = L;
12.     int x;
13.     while (scanf("%d", &x), x != -1) {
14.         tail->next = (Node*)malloc(sizeof(Node));
15.         tail = tail->next;
16.         tail->data = x;
17.     }
18.     tail->next = NULL;
19.     return L;
20. }
22. // 就地逆置链表
23. void reverseList(LinkedList L) {
24.     if (L == NULL || L->next == NULL) {
25.         return; // 空链表或仅头结点，无需逆置
26.     }
28.     Node *prev = NULL;
29.     Node *curr = L->next; // 第一个有效节点
30.     Node *next = NULL;
32.     while (curr != NULL) {
33.         next = curr->next; // 保存下一个节点
34.         curr->next = prev; // 反转当前节点的指针
35.         prev = curr;       // prev 后移
36.         curr = next;       // curr 后移
37.     }
39.     L->next = prev; // 头结点指向新的第一个节点
40. }
42. // 打印链表
43. void printList(LinkedList L) {
44.     for (Node *p = L->next; p; p = p->next) {
45.         printf("%d ", p->data);
46.     }
47.     puts("");
48. }
50. int main() {
51.     LinkedList L = createList();
52.     printf("原链表: ");
53.     printList(L);
55.     reverseList(L);
56.     printf("逆置后: ");
57.     printList(L);
59.     return 0;
60. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/)

Powered by Discuz! X3.4