如何反转双链接列表的每一半

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.splice(end(newHead), newTail);
return newHead;   
}