数据结构 ——— 单链表oj题：反转链表
目录
题目要求
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表
手搓一个简易链表
代码演示：
struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n1);
struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n2);
struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n3);
struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n4);
struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n5);
n1->val = 1;
n2->val = 3;
n3->val = 5;
n4->val = 7;
n5->val = 9;
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
n5->next = NULL;代码实现
代码演示：
struct ListNode* reverseList(struct ListNode* head)
{
if (head == NULL)
return NULL;
struct ListNode* prev = NULL;
struct ListNode* cur = head;
struct ListNode* next = cur->next;
while (cur != NULL)
{
cur->next = prev;
// 迭代
prev = cur;
cur = next;
if(next != NULL)
next = next->next;
}
return prev;
}代码解析：
代码思路：改变节点的指向，将单链表的第一个节点的 next 指向 NULL，第二个节点的 next 指向第一个节点，第三个节点的 next 指向第二个节点…………，以此类推，就完成了链表的反转
代码逻辑：利用一前（prev）一后（next）一中间（cur） 3 个节点指针进行迭代，将 cur 的 next 指向 prev，再依次往后赋值，需要注意的是 next 赋值为下一个节点的时候，要先判断 next 是否为空，再赋值，且结束的条件是中间节点为空，中间节点为空时就表示链表反转到位，最后再返回 prev 节点指针，就是新的头节点指针
代码验证：
代码的时间复杂度和空间复杂度：
while 循环执行了 N 次，每次内部是常数次，且没有开辟额外的空间，得出：
算法的时间复杂度（大O渐进表示法）：O(N)
算法的空间复杂度（大O渐进表示法）：O(1)
原文地址：https://blog.csdn.net/weixin_55341642/article/details/142689776
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！