代码拉取完成，页面将自动刷新
欢迎大家参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！
本篇将给出三种C++实现的方法
把链表放进数组中，然后通过双指针法，一前一后，来遍历数组，构造链表。
代码如下：
class Solution {
public:
void reorderList(ListNode* head) {
vector<ListNode*> vec;
ListNode* cur = head;
if (cur == nullptr) return;
while(cur != nullptr) {
vec.push_back(cur);
cur = cur->next;
}
cur = head;
int i = 1;
int j = vec.size() - 1; // i j为之前前后的双指针
int count = 0; // 计数，偶数去后面，奇数取前面
while (i <= j) {
if (count % 2 == 0) {
cur->next = vec[j];
j--;
} else {
cur->next = vec[i];
i++;
}
cur = cur->next;
count++;
}
if (vec.size() % 2 == 0) { // 如果是偶数，还要多处理中间的一个
cur->next = vec[i];
cur = cur->next;
}
cur->next = nullptr; // 注意结尾
}
};
把链表放进双向队列，然后通过双向队列一前一后弹出数据，来构造新的链表。这种方法比操作数组容易一些，不用双指针模拟一前一后了
class Solution {
public:
void reorderList(ListNode* head) {
deque<ListNode*> que;
ListNode* cur = head;
if (cur == nullptr) return;
while(cur->next != nullptr) {
que.push_back(cur->next);
cur = cur->next;
}
cur = head;
int count = 0; // 计数，偶数去后面，奇数取前面
ListNode* node;
while(que.size()) {
if (count % 2 == 0) {
node = que.back();
que.pop_back();
} else {
node = que.front();
que.pop_front();
}
count++;
cur->next = node;
cur = cur->next;
}
cur->next = nullptr; // 注意结尾
}
};
将链表分割成两个链表，然后把第二个链表反转，之后在通过两个链表拼接成新的链表。
如图：
这种方法，比较难，平均切割链表，看上去很简单，真正代码写的时候有很多细节，同时两个链表最后拼装整一个新的链表也有一些细节需要注意！
代码如下：
class Solution {
private:
// 反转链表
ListNode* reverseList(ListNode* head) {
ListNode* temp; // 保存cur的下一个节点
ListNode* cur = head;
ListNode* pre = NULL;
while(cur) {
temp = cur->next; // 保存一下 cur的下一个节点，因为接下来要改变cur->next
cur->next = pre; // 翻转操作
// 更新pre 和 cur指针
pre = cur;
cur = temp;
}
return pre;
}
public:
void reorderList(ListNode* head) {
if (head == nullptr) return;
// 使用快慢指针法，将链表分成长度均等的两个链表head1和head2
// 如果总链表长度为奇数，则head1相对head2多一个节点
ListNode* fast = head;
ListNode* slow = head;
while (fast && fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
}
ListNode* head1 = head;
ListNode* head2;
head2 = slow->next;
slow->next = nullptr;
// 对head2进行翻转
head2 = reverseList(head2);
// 将head1和head2交替生成新的链表head
ListNode* cur1 = head1;
ListNode* cur2 = head2;
ListNode* cur = head;
cur1 = cur1->next;
int count = 0; // 偶数取head2的元素，奇数取head1的元素
while (cur1 && cur2) {
if (count % 2 == 0) {
cur->next = cur2;
cur2 = cur2->next;
} else {
cur->next = cur1;
cur1 = cur1->next;
}
count++;
cur = cur->next;
}
if (cur2 != nullptr) { // 处理结尾
cur->next = cur2;
}
if (cur1 != nullptr) {
cur->next = cur1;
}
}
};
Java：
Python：
Go：
JavaScript：
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手
