剑指 Offer(第2版)面试题 24:反转链表
剑指 Offer(第2版)面试题 24:反转链表
题目来源:35. 反转链表
解法1:迭代
做烂了的题目,秒了。
代码:
/**
* 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)
{
if (head == nullptr)
return nullptr;
ListNode *pRevesedHead = nullptr;
ListNode *cur = head, *pre = nullptr;
while (cur)
{
ListNode *nxt = cur->next;
if (nxt == nullptr)
pRevesedHead = cur;
cur->next = pre;
pre = cur;
cur = nxt;
}
return pRevesedHead;
}
};
复杂度分析:
时间复杂度:O(n),其中 n 是链表的长度。需要遍历链表一次。
空间复杂度:O(1)。
解法2:递归
每次理解以后,每次都又忘了。
代码:
/**
* 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)
{
if (head == nullptr || head->next == nullptr)
return head;
ListNode *pReversedHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return pReversedHead;
}
};
复杂度分析:
时间复杂度:O(n),其中 n 是链表的长度。需要对链表的每个节点进行反转操作。
空间复杂度:O(n),其中 n 是链表的长度空间复杂度主要取决于递归调用的栈空间,最多为 n 层。