Как перевернуть каждую половину двусвязного списка? - PullRequest
Новая
       55

Как перевернуть каждую половину двусвязного списка?

0 голосов
/ 05 апреля 2020

Я пытаюсь перевернуть каждую половину двусвязного списка, допустим, что список четный, а сортировка не имеет значения.

Допустим, у меня есть этот ввод, список может иметь любое четное число элементов.

1 <=> 5 <=> 8 <=> 3 <=> 2 <=> 10

Это ожидаемый результат

8 <= > 5 <=> 1 <=> 10 <=> 2 <=> 3

Я нашел длину списка, чтобы найти среднюю позицию, затем я попытался использовать счетчик для go через каждый однако, я чувствую себя потерянным, когда начинаю делать много циклов while. Я знаю, как перевернуть весь список, но я застрял дальше. У кого-нибудь есть идеи? 



template <class T>
void DoubyLinkedList<T>:: ReverseFunction() {

node<T> *ptr = head;

//find length of list

int length = 0;
while (ptr!=NULL) {
ptr = ptr->next;
length++;
}

ptr = head;

int c = 1;
//This code reverses the whole list 
while (ptr != NULL ) {

    node<T> *tmp = ptr->next;

    ptr->next = ptr->prev;

    ptr->prev = tmp;
}

    if (tmp == NULL) {

        tail = head;
        head = ptr;

    }
    ptr = tmp;

}

}

1 Ответ

0 голосов
/ 05 апреля 2020

Я хотел бы express идея в терминах std :: list .

По сути, вырезать из головы и хвоста один элемент, создать два новых списка, а затем объединить их. Все операции O (1). 

std::list<int> reverseHalfs(std::list<int> &l) {
    assert((l.size() % 2) == 0);
    std::list<int> newHead;
    std::list<int> newTail;
    while (l.size() > 1) {
        newHead.push_front(l.front());
        newTail.push_back(l.back());
        l.pop_front();
        l.pop_back();
    }
    newHead.splice(end(newHead), newTail);
    return newHead;   
}
...