206 反转链表
迭代版
/**
* 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* prev = nullptr;
ListNode* cur = head;
while(cur){
ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
// cur指向nullptr, prev指向原链表最后一个元素(新链表头节点)
return prev;
}
};
复杂度分析
- 时间复杂度:O(n),其中 n 是链表的长度。需要遍历链表一次。
- 空间复杂度:O(1)。
递归版
和迭代法同一思路的递归版
核心思路:
- 通过递归函数依次将链表节点压栈,使算法到达链表最后一个节点再进行反转操作
- 每次递归函数执行同一反转操作,但是返回的是反转后的函数头
- 反转操作cur->next = prev(与迭代法相同)
该递归直接根据迭代法改写,while内就是递归函数体,while的条件就是递归结束的条件,另外,while后返回的值就是递归结束后返回的值
/**
* 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 {
private:
ListNode* reverse(ListNode* pre, ListNode* cur){
// 当cur为空,说明已经到达最后一个链表节点
// 此时最后一个链表节点为prev,它就是反转后的头节点
if(cur == nullptr)
return pre;
ListNode* tmp = cur->next;
cur->next = pre;
// 返回递归结束时的值
return reverse(cur, tmp);
}
public:
ListNode* reverseList(ListNode* head) {
return reverse(nullptr,head);
}
};
/**
* 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) {
if(!head || !head->next)
return head;
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
};
复杂度分析
时间复杂度:O(n),其中 n 是链表的长度。需要对链表的每个节点进行反转操作。
空间复杂度:O(n),其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间,最多为 n 层。