以特定方式将单独链接的列表一分为二

Question

你好，我遇到了这个问题，所以如果有人能指导我如何解决这个问题，这对我有很大帮助。

用C++编写一个程序，将给定的单链表的节点分为前半部分和后半部分，这样后半部分的元素就可以按相反的顺序存储。

Ex-

{1，3，4，6，2，3，8，9}->｛1，3，4，6｝和｛9，8，3，2｝

样本输入

1 3 4 6 2 3 8 9

样本输出

1 3 4 6

9 8 3 2

Answer 1

您可以如下定义Node类，包括必要的方法：

#include <iostream>
#include <vector>
class Node {
public:
int data;
Node * next { nullptr };

Node(int data) : data(data) {} 

Node(int data, Node * next) : data(data), next(next) {}
Node * extractHalf() {
Node * slow = this;
Node * fast = this->next;
if (fast == nullptr) return nullptr;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next->reverse();
slow->next = nullptr;
return fast;
}
Node * reverse() {
Node * curr = this;
Node * prev = nullptr;
while (curr != nullptr) {
Node * next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
void print() {
Node * node = this;
while (node != nullptr) {
std::cout << node->data << " -> ";
node = node->next;
}
std::cout << "NULLn";
}
static Node * fromVector(std::vector<int> v) {
Node * head = nullptr;
for (unsigned i = v.size(); i-- > 0; ) {
head = new Node(v[i], head);
}
return head;
};
};

您可以按如下方式运行它：

int main() {
Node * head = Node::fromVector({1,2,3,4,5,6,7,8});
if (head == nullptr) return 0;
std::cout << "Input list:n";
head->print();  // 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL
Node * head2 = head->extractHalf();
std::cout << "Output lists:n";
head->print();  // 1 -> 2 -> 3 -> 4 -> NULL
head2->print(); // 8 -> 7 -> 6 -> 5 -> NULL
return 0;
}