35. 反转链表
题目描述
定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。
思考题:
请同时实现迭代版本和递归版本。
数据范围
链表长度 [0,30]。
样例
输入:1->2->3->4->5->NULL
输出:5->4->3->2->1->NULL
算法1 迭代+栈+dummy
算法流程
链表所有节点入栈
弹出栈重新组装链表
最后节点next指针指向空
复杂度
时间复杂度 $O(n)$
空间复杂度 $O(n)$
C++ 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
stack<ListNode*> nodes;
ListNode* dummy = new ListNode(-1);
ListNode* p = head;
while(p)
{
nodes.push(p);
p = p->next;
}
if(nodes.empty()) return nullptr;
p = dummy;
while(!nodes.empty())
{
auto t = nodes.top();
nodes.pop();
p->next = t;
p = p->next;
}
p->next = nullptr;
return dummy->next;
}
};
算法2 y总迭代优化
算法流程
反转:将所有节点的next指针指向前驱节点
思路:用额外的指针保存前驱节点,同时在改变next指针时,保存后继节点
复杂度
时间复杂度 $O(n)$
空间复杂度 $O(1)$
C++ 代码
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; //更新
}
return prev;
}
};
算法3 递归
算法流程
函数参数:待反转链表的头节点
函数功能:将头节点所指向的链表反转
返回值:返回反转后的头节点指针,也就是原来的尾节点
反转过程:让头节点next的next指针指向头节点,头置空作为新的尾节点,返回新的头节点
复杂度
时间复杂度 $O(n)$: 每个节点遍历一次
空间复杂度 $O(n)$:递归n层,系统栈的空间复杂度是$O(n)$
C++ 代码
y总代码
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head || !head->next) return head;
ListNode* tail = reverseList(head->next); //新的头节点
head->next->next = head; //反转
head->next = nullptr; //原节点next置空
return tail;
}
};
自己代码
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head) return nullptr;
ListNode* start = reverseList(head->next);
if(!start) return head;
else
{
head->next->next = head;
head->next = nullptr;
}
return start;
}
};
总结
感觉思路到了,但是写出来的代码不优雅