我的Bilibili频道：香芋派Taro
我的个人博客：taropie0224.github.io（阅读体验更佳）
我的公众号：香芋派的烘焙坊
我的音频技术交流群：1136403177
我的个人微信：JazzyTaroPie
前置要求
面试官：请在不使用额外空间的情况下原地对链表进行操作
我：寄！
核心思想
- 首先我们知道，链表它难操作就难操作在不能即刻任意访问其中一个节点，那么我们就可以思考如何操作才能优化掉这个缺点。
- 比如我们可以新建一个vector数组，通过把原链表遍历存入vector的方式，将链表转化为vector以实现任意访问其中的某个节点。
- 按题目要求对vector进行操作（增、删、排序、交换等等等等）
- 遍历修改后的vector重新对链表的每个节点赋值（可以原地，也可以新建链表）
你必须要会的基本操作
遍历链表中的每个节点并存入vector
1
2
3
4
5
6
| vector<int> vec;
ListNode* node = head;
while (node != nullptr) {
vec.push_back(node->val);
node = node->next;
}
|
vector重新对链表的每个节点赋值（原地）
1
2
3
4
5
| node = head;
for (int i = 0; i < vec.size(); i++) {
node->val = vec[i];
node = node->next;
}
|
vector重新对链表的每个节点赋值（新建链表）
1
2
3
4
5
6
7
8
| ListNode* head = new ListNode();
ListNode* node = head;
for (int i = 0; i < vec.size(); i++) {
ListNode* cur = new ListNode();
cur->val = vec[i];
node->next = cur;
node = cur;
}
|
整个模版
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
| class Solution {
public:
ListNode* balabalaList(ListNode* head) {
if (head == nullptr) return head;
vector<int> vec;
ListNode* node = head;
while (node != nullptr) {
vec.push_back(node->val);
node = node->next;
}
......
node = head;
for (int i = 0; i < vec.size(); i++) {
node->val = vec[i];
node = node->next;
}
return head;
ListNode* head = new ListNode();
ListNode* node = head;
for (int i = 0; i < vec.size(); i++) {
ListNode* cur = new ListNode();
cur->val = vec[i];
node->next = cur;
node = cur;
}
}
};
|
举些例子
我们先来看看官方题解（归并排序）:
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
| class Solution {
public:
ListNode* sortList(ListNode* head) {
return sortList(head, nullptr);
}
ListNode* sortList(ListNode* head, ListNode* tail) {
if (head == nullptr) {
return head;
}
if (head->next == tail) {
head->next = nullptr;
return head;
}
ListNode* slow = head, *fast = head;
while (fast != tail) {
slow = slow->next;
fast = fast->next;
if (fast != tail) {
fast = fast->next;
}
}
ListNode* mid = slow;
return merge(sortList(head, mid), sortList(mid, tail));
}
ListNode* merge(ListNode* head1, ListNode* head2) {
ListNode* dummyHead = new ListNode(0);
ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
while (temp1 != nullptr && temp2 != nullptr) {
if (temp1->val <= temp2->val) {
temp->next = temp1;
temp1 = temp1->next;
} else {
temp->next = temp2;
temp2 = temp2->next;
}
temp = temp->next;
}
if (temp1 != nullptr) {
temp->next = temp1;
} else if (temp2 != nullptr) {
temp->next = temp2;
}
return dummyHead->next;
}
};
|
是不是感觉又臭又长，瞬间就不想动了？我的评价是直接开始偷鸡！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
ListNode* sortList(ListNode* head) {
if (head == nullptr) return head;
vector<int> vec;
ListNode* node = head;
while (node != nullptr) {
vec.push_back(node->val);
node = node->next;
}
sort(vec.begin(), vec.end());
node = head;
for (int i = 0; i < vec.size(); i++) {
node->val = vec[i];
node = node->next;
}
return head;
}
};
|
相较于上面总结的模版，唯一增加的就是 sort(vec.begin(), vec.end()); 这么一句话而已。
利用好余数remainder对应赋值即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (head == nullptr) return head;
vector<int> vec;
ListNode* node = head;
while (node != nullptr) {
vec.push_back(node->val);
node = node->next;
}
int len = vec.size();
int remainder = k % len;
node = head;
for (int i = 0; i < remainder; i++) {
node->val = vec[len - remainder + i];
node = node->next;
}
for (int i = 0; i < len - remainder; i++) {
node->val = vec[i];
node = node->next;
}
return head;
}
};
|
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
| class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (head == nullptr) return head;
vector<int> vec;
ListNode* node = head;
while (node != nullptr) {
vec.push_back(node->val);
node = node->next;
}
int len = vec.size();
if (len == 1) {
return nullptr;
}
vec.erase(vec.begin() + len - n);
node = head;
for (int i = 0; i < vec.size(); i++) {
node->val = vec[i];
if (i == vec.size() - 1) {
node->next = nullptr;
} else {
node = node->next;
}
}
return head;
}
};
|
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
| class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty() == true) return 0;
vector<int> vec;
for (int i = 0; i < lists.size(); i++) {
ListNode* node = lists[i];
while (node != nullptr) {
vec.push_back(node->val);
node = node->next;
}
}
sort(vec.begin(), vec.end());
ListNode* head = new ListNode();
ListNode* node = head;
for (int i = 0; i < vec.size(); i++) {
ListNode* cur = new ListNode();
cur->val = vec[i];
node->next = cur;
node = cur;
}
return head->next;
}
};
|
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
| class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (head == nullptr) return head;
vector<int> vec;
ListNode* node = head;
while (node != nullptr) {
vec.push_back(node->val);
node = node->next;
}
ListNode* Head = new ListNode();
ListNode* Node = Head;
int zheng = vec.size() / k;
int yu = vec.size() % k;
int times = -1;
for (int i = 0; i < zheng; i++) {
times = times + k;
for (int j = 0; j < k; j++) {
ListNode* cur = new ListNode;
cur->val = vec[times - j];
Node->next = cur;
Node = cur;
}
}
for (int i = 0; i < yu; i++) {
ListNode* cur = new ListNode;
cur->val = vec[times + 1 + i];
Node->next = cur;
Node = cur;
}
return Head->next;
}
};
|
总结
是不是感觉简单又无脑？再也不用纠结还要新建什么curr, prev, temp, next节点再颠来倒去弄的头晕目眩。直接秒杀Hard题好不好！
你很难在题解里找到这样通用而又无脑的解法，但是我只推荐用来应付应付面试，或者你实在走投无路了，切记不要贪杯哦！
