NO15、反转链表（贼经典，建议多多刷，不开玩笑，要闭着眼睛写出来那种）

本文主要是介绍NO15、反转链表（贼经典，建议多多刷，不开玩笑，要闭着眼睛写出来那种），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

15、反转链表

{1,2,3}

{3,2,1}

1、头插法 很经典的做法啊

struct ListNode {int val;struct ListNode* next;ListNode(int x) :val(x), next(NULL) {}
}; ListNode* ReverseList(ListNode* pHead) {struct ListNode* Head = NULL;struct ListNode* node = (ListNode*)malloc(sizeof(struct ListNode));while (pHead != nullptr) {node = pHead;pHead = pHead->next;node->next = Head;Head = node;}return Head;
}void test02()
{ListNode* head = (ListNode*)malloc(sizeof(ListNode));head->val = 1;ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));node1->val = 2;ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));node2->val = 3;ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));node3->val = 4;head->next = node1;node1->next = node2;node2->next = node3;node3->next = nullptr;auto node = ReverseList(head);while(node!=nullptr){cout << node->val << endl;node = node->next;}}

2、第二种方法，借助三个结点进行不断更替

ListNode* ReverseList(ListNode* pHead) {struct ListNode* node0 = NULL;struct ListNode* node1 = (ListNode*)malloc(sizeof(struct ListNode));struct ListNode* node2 = (ListNode*)malloc(sizeof(struct ListNode));node1 = pHead;node2 = pHead->next;while (node1 != nullptr) {node1->next = node0;node0 = node1;node1 = node2;if (node2!= nullptr) {node2 = node2 -> next;}}return node0;
}

二刷：

1、头插法来做，将元素开辟在栈上，这样会避免内存泄露

运行时间：3ms 占用内存：364k

ListNode* ReverseList(ListNode* pHead) {// 头插法if (pHead == nullptr || pHead->next == nullptr) return pHead;ListNode dummyNode = ListNode(0);ListNode* pre = &(dummyNode);pre->next = pHead;ListNode* cur = pHead->next;pHead->next = nullptr;//pre = cur;ListNode* temp = nullptr;while (cur != nullptr) {temp = cur;cur = cur->next;temp->next = pre->next;pre->next = temp;}return dummyNode.next;}

2、借助三个节点来进行迭代即可

运行时间：3ms 占用内存：504k

    ListNode* ReverseList(ListNode* pHead) {if (pHead == nullptr || pHead->next == nullptr) return pHead;ListNode * pre = nullptr,*cur = pHead,*after = pHead->next;while(cur != nullptr){//建议画个图看看就知道了cur->next = pre;pre = cur;cur = after;if(after != nullptr)after = after->next;}return pre;}

美女帅哥们如果觉得写的还行，有点用的话麻烦点个赞或者留个言支持一下阿秀~
如果觉得狗屁不通，直接留言开喷就完事了。

需要该笔记PDF版本的去个人公众号【拓跋阿秀】下回复“阿秀剑指offer笔记”即可。

这篇关于NO15、反转链表（贼经典，建议多多刷，不开玩笑，要闭着眼睛写出来那种）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！