做p2p网站的公司,建立网站的工具,网站的seo后台怎么做,找个兼职做网站的前言 题目#xff1a; 206. 反转链表 文档#xff1a; 代码随想录——反转链表 编程语言#xff1a; C 解题状态#xff1a; 有了思路以后没敢尝试 思路
需要注意的是创建指针不会申请额外的内存空间。
代码
方法一#xff1a; 双指针法/迭代
我的理解是创建了三个指针…前言 题目 206. 反转链表 文档 代码随想录——反转链表 编程语言 C 解题状态 有了思路以后没敢尝试 思路
需要注意的是创建指针不会申请额外的内存空间。
代码
方法一 双指针法/迭代
我的理解是创建了三个指针前中后各一个进行滑动。先把 n e x t next next节点保存在后面的指针中再把当前节点的 n e x t next next指针指向前面一个节点然后一起平移这三个指针。
/*** 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* tmp;ListNode* cur head;ListNode* pre nullptr;while (cur) {tmp cur - next;cur - next pre;pre cur;cur tmp;}return pre;}
};时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
方法二 递归
有点抽象不是特别理解递归代表的具体含义应该是封装了平移指针的操作。
/*** 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* reverse(ListNode* pre, ListNode* cur) {if (cur nullptr) return pre;ListNode* tmp cur - next;cur - next pre;return reverse(cur, tmp);}ListNode* reverseList(ListNode* head) {return reverse(nullptr, head);}
};时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n)空间复杂度主要取决于递归调用的栈空间最多为 n 层。
