206.Reverse Linked List
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
1
2
| Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
|
Example 2:
1
2
| Input: head = [1,2]
Output: [2,1]
|
Example 3:
1
2
| Input: head = []
Output: []
|
个人解答：
时间复杂度：O(n)
空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == nullptr)return head;
vector<int> vec;
int i = 1;
while (head != nullptr) {
vec.resize(i);
vec.push_back(head->val);
head = head->next;
i++;
}
ListNode* ans_head, * node, * end;
i--;
ans_head = new ListNode;
ans_head->val = vec[i];
end = ans_head;
while(--i) {
node = new ListNode;
node->val = vec[i];
end->next = node;
end = node;
}
end->next = NULL;
return ans_head;
}
};
|
迭代法：
时间复杂度：O(n)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
};
|
递归法：
时间复杂度：O(n)
空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
| 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;
}
};
|