C ++中的重新排序列表
假设我们有一个链表，例如l1->l2->l3->l4->…->l(n-1)->ln。我们必须将该列表重新排列为l1->ln->l2->l(n-1)->…等形式。这里的约束是，我们不能修改列表节点中的值，只能更改节点本身。因此，例如，如果列表类似于[1,2,3,4,5]，则输出将为[1,5,2,4,3]
为了解决这个问题，我们将遵循以下步骤-
定义一个称为reverse的方法来执行反向操作。这将需要节点头和节点上一个。这将如下所示-
如果head为null，则返回prev
temp：=头下
头的下一个：=上一个，和上一个：=头
返回反向（温度，上一个）
重新排序任务将如下所示-
如果head为null，则返回null
定义两个节点指针，分别称为慢速和快速，并用head初始化它们
虽然快速和快速的下一个都不为空，
慢：=慢的下一个
快速：=快速的下一个
快速：=反向（慢速的下一个）
将slow的next设置为null，并把slow：=head设置为
定义两个列表节点指针temp1和temp2
而快速不为空
temp1：=慢速下一个，temp2：=快速下一个
慢速下一个：=快速，快下一个下一个：=temp1
慢：=temp1，快：=temp2
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class ListNode{
public:
int val;
ListNode *next;
ListNode(int data){
val = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v){
ListNode *head = new ListNode(v[0]);
for(int i = 1; i<v.size(); i++){
ListNode *ptr = head;
while(ptr->next != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
void print_list(ListNode *head){
ListNode *ptr = head;
cout << "[";
while(ptr){
cout << ptr->val << ", ";
ptr = ptr->next;
}
cout << "]" << endl;
}
class Solution {
public:
ListNode* successor = NULL;
ListNode* reverse(ListNode* head, ListNode* prev = NULL){
if(!head)return prev;
ListNode* temp = head->next;
head->next = prev;
prev = head;
return reverse(temp, prev);
}
void reorderList(ListNode* head) {
if(!head)return;
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
}
fast = reverse(slow->next);
slow->next = NULL;
slow = head;
ListNode *temp1, *temp2;
while(fast){
temp1 = slow->next;
temp2 = fast->next;
slow->next = fast;
fast->next = temp1;
slow = temp1;
fast = temp2;
}
}
};
main(){
vector<int> v = {1,2,3,4,5};
ListNode *h1 = make_list(v);
Solution ob;
(ob.reorderList(h1));
print_list(h1);
}输入值
[1,2,3,4,5]
输出结果
[1, 5, 2, 4, 3, ]