双链表的反转

#include 
#include 
#include 
using namespace std;


//双链表定义 
struct DoubleListNode {
    int value;
    DoubleListNode *next;
    DoubleListNode *last;

    DoubleListNode(int data) : value(data), next(NULL), last(NULL) {}
};

//双链表反转
DoubleListNode *reverseDoubleList(DoubleListNode *head) {
    if (head == NULL) return head;

    DoubleListNode *pre = NULL;
    DoubleListNode *next = NULL;
    while (head != NULL) {
        next = head->next;
        head->next = pre;
        head->last = next;
        pre = head;
        head = next;
    }
    return pre;
}


DoubleListNode *generateRandomDoubleList(int len, int value) {
    int size = rand() % (len + 1);
    if (size == 0) return NULL;

    size--;

    DoubleListNode *head = new DoubleListNode(rand() % (value + 1));
    DoubleListNode *pre = head;
    while (size != 0) {
        DoubleListNode *cur = new DoubleListNode(rand() % (value + 1));
        pre->next = cur;
        cur->last = pre;
        pre = cur;
        size--;
    }
    return head;
}


vector<int> getDoubleListOriginOrder(DoubleListNode *head) {
    vector<int> ans;
    while (head != NULL) {
        ans.push_back(head->value);
        head = head->next;
    }
    return ans;
}


bool checkDoubleListReverse(vector<int> &origin, DoubleListNode *head) {
    DoubleListNode *end = NULL;
    for (int i = origin.size() - 1; i >= 0; i--) {
        if (origin[i] != head->value) {
            return false;
        }
        end = head;
        head = head->next;
    }
    for (int i = 0; i < origin.size(); i++) {
        if (origin[i] != end->value) {
            return false;
        }
        end = end->last;
    }
    return true;
}

int main(){
    int len = 50;
    int value = 100;
    int testTime = 100000;
    
    srand(time(0));


    cout << "Test begin:" << endl;
    for (int i = 0; i < testTime; i++) {
        DoubleListNode *node = generateRandomDoubleList(len, value);
        vector<int> arr = getDoubleListOriginOrder(node);
        node = reverseDoubleList(node);
        if (!checkDoubleListReverse(arr, node)) {
            cout << "Oops!" << endl;
            break;
        }
    }
    cout << "Test Finished!" << endl;
    return 0;
}