如何反转双向链表的每一半？

Question

我正在尝试反转双向链表的每一半，假设该列表是偶数，并且排序无关紧要。

可以说我有这个输入，该列表可以包含任何偶数个元素。

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

这是预期的输出

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

我找到了列表的长度，找到了中间位置，然后尝试使用计数器遍历每半，但是，一旦开始执行很多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;

}

}

Answer 1

我将用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.insert(end(newHead), begin(newTail), end(newTail));
    return newHead;   
}