【数据结构】设有一带头结点的单链表，编程将链表颠倒过来。要求不用另外的数组或结点完成。

ops/2024/9/23 18:52:12/

编程题：

设有一带头结点的单链表，编程将链表颠倒过来。要求不用另外的数组或结点完成。

在这里插入图片描述

分析：
该算法通过维护三个指针（prev、curr 和 next）逐步遍历单链表，实现链表的逆转。在遍历过程中，curr 的 next 指针被更新为指向 prev，逐步反转指向。最终，头结点的 next 指针指向新的头节点（即原链表的尾节点），从而完成链表的逆转。这一过程只需 (O(n)) 的时间复杂度和 (O(1)) 的空间复杂度。

#include <stdio.h>#if 0
typedef int ElemType;typedef struct Lnode {ElemType data; // 数据域struct Lnode* next; // 指针域
} Lnode, * LinkList;// 创建带头结点的单链表
LinkList createList() {LinkList head = (LinkList)malloc(sizeof(Lnode));head->next = NULL;// 这里可以添加其他节点以构造链表return head;
}// 逆转带头结点的单链表
void reverseList(LinkList head) {Lnode* prev = NULL;Lnode* curr = head->next; // 从头结点的下一个开始Lnode* next;while (curr) {next = curr->next; // 保存下一个节点curr->next = prev; // 反转当前节点的指针prev = curr; // 移动 prev 指针curr = next; // 移动 curr 指针}head->next = prev; // 头结点的 next 指向新的头结点
}// 打印链表
void printList(LinkList head) {Lnode* temp = head->next; // 从头结点的下一个开始while (temp) {printf("%d -> ", temp->data);temp = temp->next;}printf("NULL\n");
}int main() {LinkList list = createList();// 添加十个节点到链表for (int i = 1; i <= 10; i++) {Lnode* newNode = (Lnode*)malloc(sizeof(Lnode));newNode->data = i;newNode->next = NULL;Lnode* temp = list; // 找到链表的最后一个节点while (temp->next) {temp = temp->next;}temp->next = newNode; // 将新节点添加到链表末尾}printf("Original List:\n");printList(list);reverseList(list);printf("Reversed List:\n");printList(list);// 释放链表的内存Lnode* temp;while (list->next) {temp = list->next;list->next = temp->next;free(temp);}free(list);return 0;
}#endif

在这里插入图片描述

考试写：

// 逆转带头结点的单链表
void reverseList(LinkList head) {Lnode* prev = NULL;Lnode* curr = head->next; // 从头结点的下一个开始Lnode* next;while (curr) {next = curr->next; // 保存下一个节点curr->next = prev; // 反转当前节点的指针prev = curr; // 移动 prev 指针curr = next; // 移动 curr 指针}head->next = prev; // 头结点的 next 指向新的头结点
}