要反转一个单向链表,可以使用三个指针分别指向当前节点、前一个节点和后一个节点。然后,通过修改指针的指向来实现链表的反转。
具体步骤如下:
初始化三个指针:当前节点指针cur指向链表的头节点,前一个节点指针prev为NULL,后一个节点指针next为NULL。遍历链表,直到当前节点指针cur为NULL。在遍历过程中,先将后一个节点指针next指向当前节点cur的下一个节点。然后将当前节点指针cur的下一个节点指向前一个节点prev。然后将前一个节点指针prev指向当前节点指针cur。最后将当前节点指针cur指向后一个节点指针next。重复步骤2-6,直到遍历完整个链表。最后,将链表的头节点指针指向前一个节点指针prev,即可完成链表的反转。下面是一个示例代码实现:
#include<stdio.h>#include<stdlib.h>// 定义链表节点结构体struct Node { int data; struct Node* next;};// 反转链表函数struct Node* reverseLinkedList(struct Node* head) { struct Node* cur = head; struct Node* prev = NULL; struct Node* next = NULL; while (cur != NULL) { next = cur->next; // 暂存当前节点的下一个节点 cur->next = prev; // 将当前节点的下一个节点指向前一个节点,实现翻转 prev = cur; // 前一个节点指针后移 cur = next; // 当前节点指针后移 } head = prev; // 将链表头节点指向翻转后的链表的头节点 return head;}// 打印链表函数void printLinkedList(struct Node* head) { struct Node* cur = head; while (cur != NULL) { printf("%d ", cur->data); cur = cur->next; } printf("\n");}int main() { // 创建链表 struct Node* head = (struct Node*)malloc(sizeof(struct Node)); struct Node* second = (struct Node*)malloc(sizeof(struct Node)); struct Node* third = (struct Node*)malloc(sizeof(struct Node)); head->data = 1; head->next = second; second->data = 2; second->next = third; third->data = 3; third->next = NULL; printf("原始链表:"); printLinkedList(head); // 反转链表 head = reverseLinkedList(head); printf("反转后的链表:"); printLinkedList(head); // 释放内存 free(head); free(second); free(third); return 0;}
以上代码创建了一个包含3个节点的链表,然后调用reverseLinkedList
函数来反转链表,并使用printLinkedList
函数打印结果。最后释放动态分配的内存。
输出结果如下:
原始链表:1 2 3 反转后的链表:3 2 1