给定一个单链表 \(L：L0→L1→…→Ln-1→Ln\)
将其重新排列后变为：\(L0→Ln→L1→Ln-1→L2→Ln-2→…\)
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
我的解法
关于链表的题目，我的第一想法就是进行一定的模拟，我们需要得到最后一个节点，然后讲这个节点插入到头结点的后面，同时也需要将倒数第二个节点的的下一个节点设置为\(nullptr\), 然后当前的头结点移动2次，这么模拟的我们需要两个函数：一个函数返回一个链表的最后一个节点，另外一个函数是返回一个链表的倒数第二个节点。这么写的原因就是链表不能根据索引进行访问。这样做确实没有引入额外的空间，但是时间复杂度变为了\(O(N^2)\),代码如下
class Solution {
ListNode* the_last_node(ListNode* head){
if (head == nullptr || head->next == nullptr)
return head;
ListNode* temp = head;
while(temp->next){
temp = temp ->next;
}
return temp;
}
ListNode* the_second_last_node(ListNode* head){
if (head == nullptr || head->next == nullptr)
return nullptr;
ListNode* temp = head;
while (temp->next && temp->next->next){
temp = temp ->next;
}
return temp;
}
public:
void reorderList(ListNode* head) {
ListNode* cur_head = head;
while (cur_head && cur_head->next &&cur_head->next->next){
cout<< cur_head->val<<endl;
ListNode* cur_tail = the_last_node(cur_head);
ListNode* cur_second_tail = the_second_last_node(cur_head);
cur_second_tail->next = nullptr;
cur_tail->next = cur_head->next;
cur_head->next = cur_tail;
cur_head = cur_head->next->next;
}
return;
}
};
运行效率
还是要学会如何使用空间换取时间的效率，以及编码的方便性。一些算法的简便实现需要一定的空间作为支持。
线性表方法
因为链表不支持下标访问，所以我们无法随机访问链表中任意位置的元素。
因此比较容易想到的一个方法是，我们利用线性表存储该链表，然后利用线性表可以下标访问的特点，直接按顺序访问指定元素，重建该链表即可。代码如下：
class Solution {
public:
void reorderList(ListNode *head) {
if (head == nullptr) {
return;
}
vector<ListNode *> vec;
ListNode *node = head;
while (node != nullptr) {
vec.emplace_back(node);
node = node->next;
}
int i = 0, j = vec.size() - 1;
while (i < j) {
vec[i]->next = vec[j];
i++;
if (i == j) {
break;
}
vec[j]->next = vec[i];
j--;
}
vec[i]->next = nullptr;
}
};
运行效率
寻找链表中点 + 链表逆序 + 合并链表
class Solution {
public:
void reorderList(ListNode* head) {
if (head == nullptr)
return;
ListNode* mid = middleNode(head);
// 这个node是中间偏左的一个节点， 当然如果链表的个数是奇数个，那么这个节点显然是中间节点
// 如果链表的个数是偶数个, 那么我们返回的 mid 节点是中间偏左的节点
ListNode* l1 = head;
ListNode* l2 = mid->next;
mid->next = nullptr;
l2 = reverseList(l2);
mergeList(l1, l2);
}
// 1 -> 2
// 4 -> 3
// 1 -> 2 -> 3
// 5 -> 4
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast->next != nullptr && fast->next->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
ListNode* rever seList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
void mergeList(ListNode* l1, ListNode* l2) {
ListNode* l1_tmp;
ListNode* l2_tmp;
while (l1 != nullptr && l2 != nullptr) {
l1_tmp = l1->next;
l2_tmp = l2->next;
l1->next = l2;
l1 = l1_tmp;
l2->next = l1;
l2 = l2_tmp;
}
}
};