利用编程思维做题之反转链表
牛客网题目
1. 理解问题
给到我们的是一个单链表的头节点 pHead，要求反转后，返回新链表的头节点。
首先在心里设想能够快速理解的例子，如给你123序列，要你反转此序列如何回答？将最后一个数字3作为头，然后修改3后面跟着的数字为2，2后面的数字为1，这就是一个单链表的简单应用。需要提前考虑的问题：如何获取最后一个数字、遍历所有数值时需要区分前一个数值与后一个数值。
单链表的特点是每个节点包含一个值和一个指向下一个节点的指针，因此反转链表的过程实际上是改变每个节点的指针方向。
2. 输入输出
-
输入：单链表的头节点
pHead。 -
输出：反转后的链表的头节点。
3. 链表结构
单链表的节点通常定义为：
struct ListNode {
int val; // 节点的值
struct ListNode *next; // 指向下一个节点的指针
};
4. 制定策略
我们可以使用迭代的方法反转链表，核心思想是通过遍历链表并逐个改变指针方向。以下是具体步骤：
-
初始化指针：
-
prev指针:表示前一个数值，可以用于追踪新链表的头节点，初始为NULL。 -
curr指针：表示当前数值，用于遍历链表，初始为pHead。
-
-
遍历链表：
-
在每次循环中，保存当前节点的下一个节点
nextTemp（按123的顺序遍历所有数值）。 -
将当前节点的
next指针指向prev（相当于反转操作，如1指向空、2指向1、3指向2）。 -
更新
prev为当前节点curr（将prev后移）。 -
curr移动到下一个节点
nextTemp（curr后移）。
-
-
返回新链表的头节点：
-
当
curr为空时，prev就是新链表的头节点，即取到最后一个数值。
-
5. 实现代码
以下是反转单链表的 C 语言关键函数实现：
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* reverseList(struct ListNode* pHead) {
struct ListNode* prev = NULL; // 上一个节点
struct ListNode* curr = pHead; // 当前节点
struct ListNode* nextTemp = NULL; // 下一个节点
while (curr != NULL) {
nextTemp = curr->next; // 保存下一个节点
curr->next = prev; // 反转当前节点的指针
prev = curr; // 移动 prev 到当前节点
curr = nextTemp; // 移动到下一个节点
}
return prev; // 返回新链表的头节点
}
5.1 完整c语言代码
#include <stdio.h>
#include <stdlib.h>
// 定义单链表节点结构
struct ListNode {
int val; // 节点的值
struct ListNode *next; // 指向下一个节点的指针
};
// 反转链表的函数
struct ListNode* reverseList(struct ListNode* pHead) {
struct ListNode* prev = NULL; // 上一个节点
struct ListNode* curr = pHead; // 当前节点
struct ListNode* nextTemp = NULL; // 下一个节点
// 遍历链表
while (curr != NULL) {
nextTemp = curr->next; // 保存下一个节点
curr->next = prev; // 反转当前节点的指针
prev = curr; // 更新 prev 为当前节点
curr = nextTemp; // 移动到下一个节点
}
return prev; // 返回新链表的头节点
}
// 创建新节点的辅助函数
struct ListNode* createNode(int value) {
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = value;
newNode->next = NULL;
return newNode;
}
// 打印链表的辅助函数
void printList(struct ListNode* head) {
struct ListNode* current = head;
while (current != NULL) {
printf("%d -> ", current->val);
current = current->next;
}
printf("NULL\n");
}
// 测试代码
int main() {
// 创建链表 {1 -> 2 -> 3}
struct ListNode* head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(3);
printf("Original list:\n");
printList(head); // 输出原链表
// 反转链表
struct ListNode* reversedHead = reverseList(head);
printf("Reversed list:\n");
printList(reversedHead); // 输出反转后的链表
// 释放内存
struct ListNode* temp;
while (reversedHead != NULL) {
temp = reversedHead;
reversedHead = reversedHead->next;
free(temp);
}
return 0;
}
5.2 代码说明
-
节点定义：定义了一个
ListNode结构体，包含一个整型值和指向下一个节点的指针。 -
反转函数：
reverseList函数通过迭代的方法反转链表，更新每个节点的指针。 -
辅助函数：
-
createNode：用于创建新节点并返回节点指针。 -
printList：用于打印链表的内容，方便测试和调试。
-
-
主函数：在
main函数中创建一个链表{1 -> 2 -> 3}，调用反转函数，并打印原链表和反转后的链表。
5.3 运行结果
运行此代码时，您将看到原链表和反转后的链表的输出：
Original list:
1 -> 2 -> 3 -> NULL
Reversed list:
3 -> 2 -> 1 -> NULL
6. 时间和空间复杂度分析
-
时间复杂度：O(n)，因为我们遍历了链表一次。
-
空间复杂度：O(1)，只使用了常量级别的额外空间。
7. 总结
通过上述步骤，培养我们理解题目、分析题目到解决题目的思维，确定解决方案且成功实现了代码。抽象出这种方法，它不仅适用于链表反转的问题，也可以推广到其他需要遍历和修改链表结构的情况。
原文地址：https://blog.csdn.net/qq_39178993/article/details/142847729
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！