将单向链表按照特定的方式一分为二

Question

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

用C++编写一个程序，将给定的单向链表的节点分成前半部分和后半部分，使得后半部分元素以相反的顺序存储。

Ex-

{1, 3, 4, 6, 2, 3, 8, 9} --> {1, 3, 4, 6} and {9, 8, 3, 2}

示例输入

1 3 4 6 2 3 8 9

示例输出

1 3 4 6

9 8 3 2

Answer 1

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

#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 << "NULL\n";
    }

    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;
}

将单向链表按照特定的方式一分为二

Split the singly linked list into two in a specific manner

linked-list

c++11