问题描述

  已知双向循环链表 [x1, x2, x3, x4, ..., xn]，本题要求你将该链表转化为形如 [x1, x3, ..., xn, ..., x4, x2] 的形式，算法的时间复杂度要求为 O(n)。

提交文件格式

  只需要按照如下格式提交代码

#include"Linklist.h"
void changeList(Linklist &list){
    //在此处添加代码
}

输入输出格式

Input

  形如

n
list[0] list[1] ... list[n - 1]

  其中 n 表示链表的长度，其后 n 个元素为链表的元素值。

Output

  形如

list[0] list[2] ... list[n - 1] ... list[3] list[1]

  表示排序后的链表元素值。

测试用例

10
1 2 3 4 5 6 7 8 9 10

1 3 5 7 9 10 8 6 4 2

Linklist.h文件

#include<iostream>

using namespace std;

struct node{
	int num;
	node *prior, *next;
};

using Linklist = node*;

void changeList(Linklist &list);

int main(){
	int n;
	Linklist head, tail, point;
    head = tail = new node();
    cin >> n;
    for(int i = 0; i < n; i++){
        point = new node();
        cin >> point->num;
        tail->next = point;
        point->prior = tail;
        tail = point;
    }
    head->prior = tail;
    tail->next = head;
    changeList(head);
    point = head->next;
    while(point != head->prior){
    	cout << point->num << " ";
    	point = point->next;
	}
	cout << point->num;
	return 0;
}