题目：
用栈存储所有链表，再出栈就是反转后的链表
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| 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)
{
}
};
#include <stack>
using std::stack;
class Solution {
public:
ListNode *reverseList(ListNode *head)
{
if (head == nullptr)
return nullptr;
ListNode *p = head;
stack<ListNode *> stk;
while (p != nullptr) {
stk.push(p);
p = p->next;
}
head = stk.top();
ListNode *last = head;
stk.pop();
while (!stk.empty()) {
p = stk.top();
stk.pop();
last->next = p;
last = p;
}
last->next = nullptr;
return head;
}
};
|
看了题解也可以指用O(1)的空间复杂度
假设链表为 1→2→3→∅，我们想要把它改成 ∅←1←2←3。
在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 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;
}
};
|
