LeetCode——206（反转链表）
题目链接https://leetcode.cn/problems/reverse-linked-list/题目描述给你单链表的头节点head请你反转链表并返回反转后的链表。示例 1输入head [1,2,3,4,5] 输出[5,4,3,2,1]示例 2输入head [1,2] 输出[2,1]示例 3输入head [] 输出[]提示链表中节点的数目范围是[0, 5000]-5000 Node.val 5000进阶链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题题解思路1双指针思路通过设置pre和cur两个指针实现链表反转其中cur指针指向头结点pre指针初始化为null。首先要把 cur-next 节点用temp指针保存一下因为接下来要改变 cur-next 的指向了将cur-next 指向pre 此时已经反转了第一个节点了。接下来就是循环走如下代码逻辑了继续移动pre和cur指针。最后cur 指针指向了null循环结束链表也反转完毕了。/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* cur head; ListNode* pre nullptr; while(cur){ ListNode* temp cur - next; cur - next pre; pre cur; cur temp; } return pre; } };时间复杂度: O(n)空间复杂度: O(1)题解思路2递归思路递归法比较抽象但是其实和双指针法逻辑一致同样是当cur为空的时候循环结束不断将cur指向pre的过程。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; } };时间复杂度O(n) 空间复杂度O(n)
