链表_反转链表

链表_反转链表 一、leetcode-206二、题解1.引库2.代码-13.代码-2（递归）

---

一、leetcode-206

反转链表 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

输入：head = [1,2,3,4,5]

输出：[5,4,3,2,1]

---

二、题解 1.引库 #include <iostream> #include <cstdio> #include <cstdlib> #include <queue> #include <stack> #include <algorithm> #include <string> #include <map> #include <set> #include <vector> using namespace std; 2.代码-1

1.之前用过头插法，就是创建链表的方法进行反转 2.这次使用双指针法，一前一后进行反转

class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* temp; // 保存cur的下一个节点 ListNode* cur = head; ListNode* pre = NULL; while(cur) { temp = cur->next; // 保存一下 cur的下一个节点，因为接下来要改变cur->next cur->next = pre; // 翻转操作 // 更新pre 和 cur指针 pre = cur; cur = temp; } return pre; } }; 3.代码-2（递归）

1.reverseList(ListNode* head)返回反转链表的头节点 2.head== NULL||head->next== NULL直接返回head 3.头节点后面的节点是反转后的尾节点，反转后将头节点接在该节点之后

class Solution { public: ListNode* reverseList(ListNode* head) { // 边缘条件判断 if(head == NULL) return NULL; if (head->next == NULL) return head; // 递归调用，翻转第二个节点开始往后的链表 ListNode *last = reverseList(head->next); // 翻转头节点与第二个节点的指向 head->next->next = head; // 此时的 head 节点为尾节点，next 需要指向 NULL head->next = NULL; return last; } };